Problem Description
You are given the array paths, where paths[i] = [cityA_i, cityB_i] means there exists a direct path going from cityA_i to cityB_i. Return the destination city, that is, the city without any path outgoing to another city.
Key Insights
- The problem represents a directed acyclic graph (DAG) where each path is a directed edge.
- The destination city is defined as the city with no outgoing paths.
- We can track cities with outgoing paths using a set or a dictionary.
- After processing all paths, the city that is not in the outgoing cities set will be the destination city.
Space and Time Complexity
Time Complexity: O(n), where n is the number of paths. Space Complexity: O(n), for storing the outgoing cities.
Solution
To solve the problem, we can use a set to keep track of all cities that have outgoing paths. We will iterate through the input array paths, and for each path, we will add the starting city (cityA) to the outgoing cities set. After processing all paths, we will check which city is not in the outgoing cities set, and that will be our destination city.