Destination City

easy hash map hash set

Problem

You're given an array paths of [from, to] city pairs that describe a route. Exactly one city is never the start of any path — that's the final destination. Return it.

Inputpaths = [["London","NY"],["NY","LA"],["LA","SF"]]

Output"SF"

SF appears as destination but never as a source.

paths (JSON of [from,to])

def dest_city(paths):
    sources = {a for a, _ in paths}
    for _, b in paths:
        if b not in sources:
            return b
    return ""

function destCity(paths) {
  const sources = new Set();
  for (const [a, _] of paths) sources.add(a);
  for (const [_, b] of paths) {
    if (!sources.has(b)) return b;
  }
  return "";
}

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

string destCity(vector<vector<string>>& paths) {
    unordered_set<string> sources;
    for (auto& p : paths) sources.insert(p[0]);
    for (auto& p : paths) {
        if (!sources.count(p[1])) return p[1];
    }
    return "";
}

Explanation

The route is a straight line of cities, and the final destination is the one place you never leave from. So the answer is the city that shows up as a destination but never as a source.

The code first collects every starting city into a sources set. A hash set gives instant membership checks, which is what makes this fast.

Then it scans the to side of each path. The first city b that is not in sources has no outgoing road, so it must be the end of the trip — we return it immediately.

Example: [["London","NY"],["NY","LA"],["LA","SF"]]. Sources are {London, NY, LA}. Checking destinations, NY and LA are sources, but SF is not, so SF is the answer.

Because exactly one city qualifies, the first match is guaranteed correct, and we only make two passes over the list.

Time: O(n) Space: O(n)