Destination City

Problem Statement

In this task, you are given an array of direct paths represented as pairs, where each pair [cityAi, cityBi] indicates a direct route from cityAi to cityBi. Your goal is to determine which city is the ultimate destination of this sequence of trips. The destination city is identified as the one which does not have any other city listed as its destination in the provided array of paths. Essentially, you have to find a city from which no outgoing paths are present in the given list. This problem is set in a graph context without loops, ensuring a straightforward path leading to a unique endpoint city.

Examples

Example 1

Input:

paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]

Output:

"Sao Paulo"

Explanation:

Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2

Input:

paths = [["B","C"],["D","B"],["C","A"]]

Output:

"A"

Explanation:

All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3

Input:

paths = [["A","Z"]]

Output:

"Z"

Constraints

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

Approach and Intuition

To find the destination city, consider the following approach:

1. Track all cities that are starting points (cityAi) and all cities that are endpoints (cityBi) in separate lists or sets.
2. The destination city is simply the city that appears in the endpoint list but never appears in the starting point list. This approach leverages the problem's guarantee that the path structure forms a line without loops.

Example Analyses from Provided Examples:

• Example 1:

  • Paths: [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
  • Start Cities: London, New York, Lima
  • End Cities: New York, Lima, Sao Paulo
  • Sao Paulo is the only city among end cities that does not appear as a start city, hence it is the destination.

• Example 2:

  • Paths: [["B","C"],["D","B"],["C","A"]]
  • Start Cities: B, D, C
  • End Cities: C, B, A
  • Only A appears solely in the endpoint list, making it the destination.

• Example 3:

  • Paths: [["A","Z"]]
  • Start Cities: A
  • End Cities: Z
  • Z does not appear as a start city, therefore it's identified as the destination.

This approach systematically processes the paths to single out the destination city based on the properties of the graph formed by the paths.

Solutions

class Solution {
public:
    string findDestinationCity(vector<vector<string>>& routes) {
        unordered_set<string> citiesWithDeparture;
        for (auto& route : routes) {
            citiesWithDeparture.insert(route[0]);
        }
            
        for (auto& route : routes) {
            string target = route[1];
            if (citiesWithDeparture.find(target) == citiesWithDeparture.end()) {
                return target;
            }
        }
            
        return "";
    }
};