Problem Description

The "Destination City" problem asks you to determine the final destination city given a list of direct paths between cities. Each path is represented as a pair [cityA, cityB], meaning there is a direct path from cityA to cityB. The list forms a sequence of connected cities, and it is guaranteed that the paths form a single line (no cycles, no branches).

• You are given a list paths where each element is a pair of strings: [fromCity, toCity].
• There will always be exactly one city that is the final destination: it never appears as a starting city in any pair.
• Your task is to return the name of this destination city.

Key constraints:

• There is exactly one valid destination city.
• You do not need to handle cycles or disconnected graphs.

Thought Process

The problem is about tracing a path through a series of cities and finding the city where the journey ends. If you imagine the cities as nodes and the paths as arrows, the destination city is the one that has arrows pointing to it, but never has an arrow pointing from it.

The brute-force approach might be to simulate the journey by following the paths, but that could be inefficient. Instead, we can approach the problem by analyzing the properties of the input:

• Every city except the destination appears as a starting city at least once.
• The destination city only appears as a destination, never as a starting point.

This leads us to think about using sets or hash maps to efficiently check which cities are only destinations. This is much faster than following the paths one-by-one.

Solution Approach

Let's break down the steps for an efficient solution:

1. Collect all starting cities:
   • Go through all the paths and add the fromCity of each path to a set. This set will contain all the cities that are used as a starting point.
2. Find the city that is only a destination:
   • Go through all the paths again and check each toCity. If a toCity is not in the set of starting cities, it must be the destination city.
3. Return the destination city:
   • Since the problem guarantees there is only one destination, we can return as soon as we find it.

We use a set for starting cities because lookups in a set are O(1), making the algorithm efficient even for large input sizes.

Example Walkthrough

Suppose the input is:
paths = [["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]

1. Collect starting cities:
   • From the paths, the starting cities are: "London", "New York", "Lima".
   • Set: {"London", "New York", "Lima"}
2. Find the destination:
   • Check each destination city:
   • "New York" (in set, skip)
   • "Lima" (in set, skip)
   • "Sao Paulo" (not in set!)
   • So, "Sao Paulo" is the destination city.

The function returns "Sao Paulo".

Time and Space Complexity

• Brute-force approach:
  • If you tried to trace the path by following each connection, you might need to search for the next city at each step. This could lead to O(N^2) time complexity for N paths.
• Optimized approach (using sets):
  • Collecting all starting cities: O(N)
  • Checking each destination: O(N)
  • Total time complexity: O(N)
  • Space complexity: O(N) for storing the set of starting cities.

This efficiency is achieved by using a set for constant-time lookups.

Summary

The "Destination City" problem is best solved by recognizing that the destination is the only city never used as a starting point. By collecting all starting cities in a set, we can quickly check which city is the unique destination. This approach is both simple and efficient, making excellent use of data structures for fast lookups. The key insight is that the problem reduces to set membership, not path traversal.

Code Implementation

class Solution:
    def destCity(self, paths):
        starts = set()
        for path in paths:
            starts.add(path[0])
        for path in paths:
            if path[1] not in starts:
                return path[1]
      

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> starts;
        for (const auto& path : paths) {
            starts.insert(path[0]);
        }
        for (const auto& path : paths) {
            if (starts.find(path[1]) == starts.end()) {
                return path[1];
            }
        }
        return "";
    }
};
      

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> starts = new HashSet<>();
        for (List<String> path : paths) {
            starts.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (!starts.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return "";
    }
}
      

var destCity = function(paths) {
    const starts = new Set();
    for (const path of paths) {
        starts.add(path[0]);
    }
    for (const path of paths) {
        if (!starts.has(path[1])) {
            return path[1];
        }
    }
};