Destination City

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

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.

from typing import List

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

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, string> mp;
        for (auto& p : paths) {
            mp[p[0]] = p[1];
        }

        string start = paths[0][0];
        while (mp.find(start) != mp.end()) {
            start = mp[start];
        }
        return start;
    }
};