1436. Destination City
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 77.3%
Problem Breakdown
The problem asks us to find the destination city from a list of paths where each path is represented as a pair of cities [cityAi, cityBi]. The destination city is defined as the city that does not appear as a starting point in any path. Given the constraints, we know that the graph formed by these paths will always be a line without loops, ensuring there is exactly one destination city.
Inputs:
paths: A list of lists where each sublist contains two strings representing a direct path fromcityAitocityBi.
Outputs:
- A string representing the destination city that has no outgoing paths.
Implicit Constraints:
- The graph forms a line without loops.
- There is exactly one destination city.
- All city names are non-empty and consist of lowercase and uppercase English letters and spaces.
Intuition
A brute-force approach would involve checking each city to see if it appears as a starting point in any path. This would require iterating over the list of paths multiple times, leading to a time complexity of O(n^2), which is inefficient for larger inputs.
The key insight is that the destination city will never appear as a starting point in any path. Therefore, we can use a set to store all cities that have outgoing paths and then find the city that is not in this set.
Approach
- Initialize an empty set
outgoing_citiesto keep track of cities that have outgoing paths. - Iterate through each path in the input list:
- Add the starting city (
cityAi) of the current path to theoutgoing_citiesset.
- Add the starting city (
- After populating the set, iterate through each path again:
- For each destination city (
cityBi), check if it is not in theoutgoing_citiesset. - The first such city found will be the destination city.
- For each destination city (
Complexity Analysis
- Time Complexity: O(n), where n is the number of paths. We iterate through the list of paths twice, each time taking linear time.
- Space Complexity: O(n), as we store all starting cities in a set, which could potentially contain up to n elements.
Solution
def destCity(paths):
outgoing_cities = set()
# Collect all cities that have outgoing paths
for path in paths:
outgoing_cities.add(path[0])
# Find the city that does not have an outgoing path
for path in paths:
if path[1] not in outgoing_cities:
return path[1]
# Example usage:
paths1 = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
print(destCity(paths1)) # Output: "Sao Paulo"
paths2 = [["B","C"],["D","B"],["C","A"]]
print(destCity(paths2)) # Output: "A"
paths3 = [["A","Z"]]
print(destCity(paths3)) # Output: "Z"
Edge Cases Handled
- Single Path: The code handles the case where there is only one path, correctly identifying the destination city as the end of that path.
- No Paths: Although not explicitly mentioned in the problem constraints, if
pathswere empty, the function would returnNonebecause it would not find any cities to process. This could be handled by adding a check at the beginning of the function to return an appropriate message or value for such cases.