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 != cityBiThe idea is to determine which city does not have any outgoing paths. This can be done by keeping track of all cities that appear as the starting city of a path. The destination city is the one that is not in this set but appears as an ending city in the path list.
This C solution uses an array to simulate a set to track which cities have outgoing paths. We iterate over the paths, storing cities in an array and marking those that appear as starting cities. Finally, we check which city does not appear as a starting city and return it as the destination.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to linear checks within loops.
Space Complexity: O(n), where n is the number of cities.
This approach involves counting occurrences of each city as an endpoint. The destination city will be the one whose occurrence as a destination is not matched by an occurrence as a start.
This C solution involves copying the destination cities into an array and checking each destination city against the start cities. The city not found among the start cities is returned as the destination city.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), since it includes iterating through paths multiple times.
Space Complexity: O(n) for storing city names.
| Approach | Complexity |
|---|---|
| Using a Set to Track Cities with Outgoing Paths | Time Complexity: O(n^2) due to linear checks within loops. |
| Track and Count Incoming Cities | Time Complexity: O(n^2), since it includes iterating through paths multiple times. |
Destination City - Leetcode 1436 - Python • NeetCodeIO • 7,223 views views
Watch 9 more video solutions →Practice Destination City with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor