Sponsored
Sponsored
The 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.
Time Complexity: O(n^2) due to linear checks within loops.
Space Complexity: O(n), where n is the number of cities.
1def destCity(paths):
2 starting_cities = set()
3 for path in paths:
4 starting_cities.add(path[0])
5 for path in paths:
6 if path[1] not in starting_cities:
7 return path[1]This Python solution uses a set to track each of the starting cities. For each path, it checks if the destination is not in the set of starting cities. The first such city found is the destination city.
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.
Time Complexity: O(n^2), since it includes iterating through paths multiple times.
Space Complexity: O(n) for storing city names.
1#
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.