Problem Description

You are given an array paths where each element paths[i] = [cityAi, cityBi] represents a direct path from cityAi to cityBi. Your task is to find the destination city - the city that has no outgoing paths to any other city.

The problem guarantees that the paths form a linear graph without any loops, meaning there will be exactly one destination city.

For example, if you have paths like [["A", "B"], ["B", "C"], ["C", "D"]], the destination city would be "D" because it has no outgoing path to another city.

The solution uses a hash table approach. First, it collects all starting cities (cityA values) into a set s. Then it finds the ending city (cityB) that doesn't appear in this set - this must be the destination city since it never appears as a starting point for any path.

The key insight is that every city except the destination will appear as a starting point in at least one path. The destination city only appears as an ending point (cityB) but never as a starting point (cityA).

Intuition

To find the destination city, we need to identify which city we can only arrive at but never leave from. Let's think about the structure of the paths - since they form a line without loops, we have a chain of cities connected one after another.

In this chain, every city except the last one must have an outgoing path. The destination city is special because it only appears as an endpoint (cityB) in the paths but never as a starting point (cityA).

This observation leads us to a simple strategy: if we collect all the cities that appear as starting points, then the destination city must be the one city that appears as an endpoint but is not in our collection of starting points.

For example, with paths [["London","New York"], ["New York","Lima"], ["Lima","Sao Paulo"]]:

• Starting cities: {"London", "New York", "Lima"}
• Ending cities: {"New York", "Lima", "Sao Paulo"}
• The city "Sao Paulo" appears as an ending city but not as a starting city, so it's our destination.

This approach works because in a linear path structure, every intermediate city must have exactly one incoming and one outgoing path, while the destination city only has an incoming path. By tracking which cities have outgoing paths (appear as cityA), we can quickly identify the unique city that doesn't - our destination.

Solution Approach

The implementation uses a hash table (set) to efficiently solve this problem:

1. Build a set of starting cities: We iterate through all paths and extract the first city (cityA) from each path using list comprehension with unpacking: s = {a for a, _ in paths}. This creates a set containing all cities that have outgoing paths.

2. Find the destination city: We iterate through the paths again and check each ending city (cityB). Using a generator expression with next(), we find the first cityB that is not in our set s: return next(b for _, b in paths if b not in s).

The algorithm works as follows:

• Time Complexity: O(n) where n is the number of paths. We traverse the paths twice - once to build the set and once to find the destination.
• Space Complexity: O(n) for storing the set of starting cities.

The use of set data structure is crucial here because:

• Set creation from the starting cities is O(n)
• Checking membership (b not in s) is O(1) on average for sets

The next() function with a generator expression is an efficient way to find and return the first element that satisfies our condition without creating an intermediate list. As soon as we find a cityB that's not in the set of starting cities, we immediately return it as our answer.

This approach elegantly leverages the property that in a linear path graph, only the destination city never appears as a starting point.

Example Walkthrough

Let's walk through a small example with paths: [["A", "B"], ["B", "C"], ["C", "D"]]

Step 1: Build the set of starting cities

We iterate through each path and collect all cityA values:

• Path ["A", "B"] → Add "A" to set
• Path ["B", "C"] → Add "B" to set
• Path ["C", "D"] → Add "C" to set

Result: s = {"A", "B", "C"}

These are all cities that have outgoing paths (cities we can leave from).

Step 2: Find the destination city

Now we check each ending city (cityB) to see if it's in our set:

• Path ["A", "B"] → Check "B": Is "B" in s? Yes (it's in {"A", "B", "C"}), skip
• Path ["B", "C"] → Check "C": Is "C" in s? Yes (it's in {"A", "B", "C"}), skip
• Path ["C", "D"] → Check "D": Is "D" in s? No (it's not in {"A", "B", "C"}), found it!

Return "D" as the destination city.

Why this works:

• Cities "A", "B", and "C" all appear as starting points, meaning we can leave from them
• City "D" only appears as an ending point, never as a starting point
• This means "D" is the city we can only arrive at but never leave from - our destination!

The visual path looks like: A → B → C → D, where D is the final destination with no outgoing paths.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of paths. The algorithm iterates through the paths list twice - once to build the set s containing all starting cities (which takes O(n) time), and once more in the worst case to find the destination city that is not in the set (which also takes O(n) time). Since these operations are sequential, the overall time complexity is O(n) + O(n) = O(n).

The space complexity is O(n), where n is the length of paths. This is because the set s stores all the starting cities from the paths. In the worst case, each path has a unique starting city, so the set would contain n elements, requiring O(n) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Multiple Destination Cities

A common mistake is not trusting the problem guarantee that there's exactly one destination city. Some might try to handle multiple destinations or add unnecessary validation:

# Incorrect: Trying to handle multiple destinations
destinations = [b for _, b in paths if b not in departure_cities]
if len(destinations) != 1:
    raise ValueError("Invalid input")
return destinations[0]

Solution: Trust the problem constraints. The linear graph property guarantees exactly one destination, so using next() without a default value is safe and more efficient.

2. Using List Instead of Set for Departure Cities

Using a list to store departure cities significantly degrades performance:

# Inefficient: O(n²) time complexity
departure_cities = [a for a, _ in paths]  # List instead of set
return next(b for _, b in paths if b not in departure_cities)  # O(n) lookup

Solution: Always use a set for membership testing. Set lookup is O(1) average case, while list lookup is O(n).

3. Iterating Through All Cities Instead of Just Paths

Some might try to first collect all unique cities, then check which one has no outgoing paths:

# Inefficient: Extra iteration and storage
all_cities = set()
for a, b in paths:
    all_cities.add(a)
    all_cities.add(b)
  
for city in all_cities:
    if city not in departure_cities:
        return city

Solution: The destination city must appear as an ending city in at least one path. Checking only the cityB values from paths is sufficient and more efficient.

4. Not Handling Edge Cases

While the problem guarantees valid input, in real-world scenarios you might want to handle:

• Empty paths array
• Single path (though this works correctly with the given solution)

# More robust version with edge case handling
def destCity(self, paths: List[List[str]]) -> str:
    if not paths:
        return ""  # or raise an exception
  
    departure_cities = {a for a, _ in paths}
    return next(b for _, b in paths if b not in departure_cities)