Destination City

Difficulty: Easy | Acceptance: 79.50% | Paid: No Topics: Array, Hash Table, String

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

• Examples
• Constraints
• Hash Set
• Brute Force

Examples

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" you end the trip at "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

Constraints

1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
All strings consist of lowercase and uppercase English letters and the space character.

Hash Set

Intuition The destination city is the only city that never appears as a starting point in any path. By collecting all starting cities in a set, we can efficiently check which ending city is not in that set.

Steps

• Initialize an empty set to store cities that have outgoing paths.
• Iterate through the paths list and add the starting city (index 0) of each path to the set.
• Iterate through the paths list again. For each path, check if the destination city (index 1) is present in the set.
• The first destination city not found in the set is the answer.

from typing import List

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        outgoing = set()
        for path in paths:
            outgoing.add(path[0])
        for path in paths:
            if path[1] not in outgoing:
                return path[1]
        return ""

Complexity

• Time: O(N), where N is the number of paths. We iterate through the list twice.
• Space: O(N), to store the set of outgoing cities.
• Notes: This is the optimal solution for this problem.

Brute Force

Intuition For every city that appears as a destination, we can check if it ever appears as a departure in the entire list of paths. The city that never appears as a departure is our answer.

Steps

• Iterate through the paths list to collect all destination cities into a list.
• For each candidate destination city, iterate through the paths list again to see if it exists as a starting city.
• If a candidate city is never found as a starting city, return it.

from typing import List

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        destinations = [path[1] for path in paths]
        for dest in destinations:
            is_start = False
            for path in paths:
                if path[0] == dest:
                    is_start = True
                    break
            if not is_start:
                return dest
        return ""

Complexity

• Time: O(N²), where N is the number of paths. For each destination, we scan the entire list of paths.
• Space: O(N), to store the list of destination cities.
• Notes: This approach is inefficient for large inputs but is conceptually simple.