1436. Destination City - Explanation

Problem Link

1. Brute Force

Intuition

The destination city is a city that appears as an endpoint but never as a starting point in any path. For each destination in the paths, we can check whether it ever appears as a starting city. The city that never starts a path is our answer.

Algorithm

1. Iterate through each path and consider its destination city.
2. For each destination, iterate through all paths again to check if this city appears as a starting point.
3. If the destination never appears as a starting point in any path, return it as the answer.
4. Return an empty string if no destination city is found (though the problem guarantees one exists).

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        for i in range(len(paths)):
            flag = True
            for j in range(len(paths)):
                if paths[i][1] == paths[j][0]:
                    flag = False
                    break
            if flag:
                return paths[i][1]
        return ""

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

---

2. Hash Set

Intuition

Instead of checking each destination against all starting points in O(n) time, we can store all starting cities in a hash set for O(1) lookup. Any destination city that is not in the set of starting cities must be the final destination.

Algorithm

1. Create a hash set and add all starting cities (the first element of each path) to it.
2. Iterate through all paths and check each destination city (the second element).
3. If a destination city is not found in the hash set, return it as the answer.
4. The first destination not in the set is the final destination city.

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        s = set()
        for p in paths:
            s.add(p[0])

        for p in paths:
            if p[1] not in s:
                return p[1]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Hash Map

Intuition

We can model the paths as a linked chain where each city points to its next destination. By building this chain in a hash map and following the links from any starting city, we will eventually reach the final destination, which has no outgoing path.

Algorithm

1. Build a hash map where each key is a starting city and its value is the destination city.
2. Start with the first city from the first path.
3. Keep following the chain: while the current city exists as a key in the map, move to its destination.
4. When the current city is not a key in the map, it means there is no outgoing path from it, return it as the destination city.

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        mp = {p[0]: p[1] for p in paths}

        start = paths[0][0]
        while start in mp:
            start = mp[start]
        return start

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Adding Both Cities to the Set

When using the hash set approach, only starting cities should be added to the set. Adding both starting and ending cities defeats the purpose since you need to find which destination is never a starting point.

# Wrong - adds both cities
for p in paths:
    s.add(p[0])
    s.add(p[1])  # Incorrect: this includes destinations

# Correct - only add starting cities
for p in paths:
    s.add(p[0])

Checking Starting Cities Instead of Destinations

A common logic error is checking if starting cities are absent from the set of destinations, rather than checking if destinations are absent from the set of starting cities.

# Wrong - checking the wrong direction
s = set(p[1] for p in paths)  # Set of destinations
for p in paths:
    if p[0] not in s:  # Looking for start with no incoming path
        return p[0]

# Correct - find destination with no outgoing path
s = set(p[0] for p in paths)  # Set of starting cities
for p in paths:
    if p[1] not in s:  # Destination that is never a start
        return p[1]