Destination City

In this problem, we’re given a list of pairs representing cities, where the first city in each pair has a direct path to the second city. Our task is to find the city that doesn’t have any outgoing paths, meaning it’s not the first city in any of the pairs. In other words, it’s the destination city.

We can solve this problem by creating two sets of cities: one for cities that have outgoing paths (the first city in each pair), and another for cities that are at the end of a path (the second city in each pair). The destination city will be the one that’s in the second set but not in the first.

Here’s the Python code for this solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        # Create a set of cities that have outgoing paths
        start_cities = set()
        for path in paths:
            start_cities.add(path[0])

        # Find the city that's at the end of a path but doesn't have any outgoing paths
        for path in paths:
            if path[1] not in start_cities:
                return path[1]

In this code, we first create a set of cities that have outgoing paths by iterating over the list of paths and adding the first city from each pair to the set. Then we find the city that’s at the end of a path (the second city in a pair) but isn’t in the set of cities with outgoing paths, meaning it’s the destination city. This is the city we return.