Watch 10 video solutions for Destination City, a easy level problem involving Array, Hash Table, String. This walkthrough by NeetCodeIO has 7,921 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] Output: "Sao Paulo" Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "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 <= 100paths[i].length == 21 <= cityAi.length, cityBi.length <= 10cityAi != cityBiProblem Overview: You are given a list of travel paths where paths[i] = [cityA, cityB] means there is a direct trip from cityA to cityB. The paths form a line without cycles. Your task is to find the final destination city — the one that never appears as a starting city.
Approach 1: Using a Set to Track Cities with Outgoing Paths (O(n) time, O(n) space)
The key observation: the destination city never appears as a starting city in any path. Iterate through the list and insert every cityA into a hash set. This set represents all cities that have outgoing paths. Then iterate through the paths again and check each cityB. The first city not present in the set must be the final destination. Hash lookups run in constant time, so the entire process takes linear time relative to the number of paths. This method uses a hash table or set for efficient membership checks and works well for general cases.
Approach 2: Track and Count Incoming Cities (O(n) time, O(n) space)
Another way to think about the problem is through incoming edges. Every intermediate city appears both as a destination and as a starting city. The final city appears only as a destination. Use a hash map to count incoming occurrences for each city while also tracking cities that start paths. Iterate through all pairs in the array of paths and increment the count for cityB. After processing all paths, scan the map and return the city that has incoming paths but never appears as a start city. This approach models the travel routes like a simple directed graph and uses efficient lookups from a hash table.
Recommended for interviews: The set-based approach is usually what interviewers expect. It shows you quickly identified the key property: the destination city has zero outgoing edges. The implementation is concise and runs in O(n) time with O(n) space. Mentioning the graph interpretation (incoming vs outgoing edges) demonstrates deeper understanding of how the problem relates to common patterns in string and path traversal problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set of Cities with Outgoing Paths | O(n) | O(n) | Best general solution. Simple logic with fast hash lookups. |
| Track Incoming Cities with Map | O(n) | O(n) | Useful when modeling the paths as directed graph edges. |