Domain 1EasyCORE

Destination City

The problem asks us to find the destination city from a list of paths where each path is represented as a pair of cities `[cityAi, cityBi]`. The destination city is defined as the city that does not appear as a starting point in any path. Given the constraints, we know that the graph formed by these paths will always be a line without loops, ensuring there is exactly one destination city.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1436. Destination City

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 77.3%


Problem Breakdown

The problem asks us to find the destination city from a list of paths where each path is represented as a pair of cities [cityAi, cityBi]. The destination city is defined as the city that does not appear as a starting point in any path. Given the constraints, we know that the graph formed by these paths will always be a line without loops, ensuring there is exactly one destination city.

Inputs:

  • paths: A list of lists where each sublist contains two strings representing a direct path from cityAi to cityBi.

Outputs:

  • A string representing the destination city that has no outgoing paths.

Implicit Constraints:

  • The graph forms a line without loops.
  • There is exactly one destination city.
  • All city names are non-empty and consist of lowercase and uppercase English letters and spaces.

Intuition

A brute-force approach would involve checking each city to see if it appears as a starting point in any path. This would require iterating over the list of paths multiple times, leading to a time complexity of O(n^2), which is inefficient for larger inputs.

The key insight is that the destination city will never appear as a starting point in any path. Therefore, we can use a set to store all cities that have outgoing paths and then find the city that is not in this set.

Approach

  1. Initialize an empty set outgoing_cities to keep track of cities that have outgoing paths.
  2. Iterate through each path in the input list:
    • Add the starting city (cityAi) of the current path to the outgoing_cities set.
  3. After populating the set, iterate through each path again:
    • For each destination city (cityBi), check if it is not in the outgoing_cities set.
    • The first such city found will be the destination city.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of paths. We iterate through the list of paths twice, each time taking linear time.
  • Space Complexity: O(n), as we store all starting cities in a set, which could potentially contain up to n elements.

Solution

def destCity(paths):
    outgoing_cities = set()
    
    # Collect all cities that have outgoing paths
    for path in paths:
        outgoing_cities.add(path[0])
    
    # Find the city that does not have an outgoing path
    for path in paths:
        if path[1] not in outgoing_cities:
            return path[1]

# Example usage:
paths1 = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
print(destCity(paths1))  # Output: "Sao Paulo"

paths2 = [["B","C"],["D","B"],["C","A"]]
print(destCity(paths2))  # Output: "A"

paths3 = [["A","Z"]]
print(destCity(paths3))  # Output: "Z"

Edge Cases Handled

  • Single Path: The code handles the case where there is only one path, correctly identifying the destination city as the end of that path.
  • No Paths: Although not explicitly mentioned in the problem constraints, if paths were empty, the function would return None because it would not find any cities to process. This could be handled by adding a check at the beginning of the function to return an appropriate message or value for such cases.