Destination City: Hash Set Lookup Pattern
You are given an array paths where paths[i] = [cityA_i, cityB_i] means there is a direct path from cityA_i to cityB_i. The paths form a line without any cycles, and there is exactly one city that has no outgoing path. Find that city.
This is LeetCode 1436: Destination City, and it is a clean introduction to using a hash set for membership testing. The problem boils down to one observation: the destination city is the only city that never appears as a source.
Why this problem matters
Destination City teaches you to think about relationships in terms of sets. Instead of building a full graph and searching for a terminal node, you can solve it by asking a simpler question: "which value appears on one side of the pairs but not the other?" This set-based reasoning shows up in many interview problems. When you need to find the element that is missing, unique, or unmatched, building a set and checking membership is often the fastest path.
The technique here is the same one you use in problems like "Find the Town Judge" (checking who never trusts anyone) and "Happy Number" (detecting a value you have seen before). Collect one group of values into a set, then scan another group to find the outlier.
The key insight
Every path [a, b] tells you that city a has at least one outgoing route. The destination city is the one that never appears as city a in any path. So you collect all source cities (the left side of each pair) into a set, then look through all destination cities (the right side of each pair) to find the one missing from that set.
You do not need to build an adjacency list. You do not need to traverse anything. One set and two scans through the paths list is all it takes.
The solution
def dest_city(paths: list[list[str]]) -> str:
sources = set()
for a, b in paths:
sources.add(a)
for a, b in paths:
if b not in sources:
return b
The first loop builds a set of every city that appears as a source (the left element of each pair). The second loop checks each destination city (the right element) against that set. The city that is not in the source set has no outgoing path, so it must be the destination.
Why does this work? The problem guarantees a single linear chain with no cycles. That means exactly one city appears only as a destination and never as a source. Every other city appears as a source at least once. The set lookup b not in sources runs in O(1) on average, so the check is fast.
When a problem asks you to find the element that is "missing" from one group but present in another, your first instinct should be to build a set from the first group. Set membership testing in O(1) turns what could be an O(n^2) nested-loop search into an O(n) scan.
Visual walkthrough
Step 1: Collect all source cities into a set
Scan each path [a, b] and add the source city a to the set. These are cities that have at least one outgoing path.
sources = {"London", "New York", "Lima"}
Process [London, New York], [New York, Lima], [Lima, Sao Paulo]. Each left-side city goes into the set.
Step 2: Scan destination cities and find the one not in the source set
Now scan each path [a, b] again and check if the destination city b appears in the source set. The one that does not appear is the answer.
"Sao Paulo" is not in sources. It is the destination city.
New York and Lima are both sources. Sao Paulo never appears as a source, so it has no outgoing path. Return "Sao Paulo".
The entire algorithm is just two passes over the paths array. The first pass fills the set, the second pass finds the answer. No graph traversal, no recursion, no sorting. The set does all the heavy lifting.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Hash set lookup | O(n) | O(n) |
Time is O(n) where n is the number of paths. The first loop iterates through all n paths to build the source set. The second loop iterates through at most n paths to find the destination. Each set insertion and lookup is O(1) on average.
Space is O(n) for the source set. In the worst case, the set contains n entries (one for each source city).
The building blocks
1. Collecting values into a set for membership testing
The core pattern is extracting one "column" from a list of pairs and putting it into a set for fast lookups:
sources = set()
for a, b in paths:
sources.add(a)
This is the same idea used whenever you need to check "does this value exist in a group?" in O(1). You will see it in Two Sum (checking if the complement exists), Contains Duplicate (checking if you have seen this number before), and any problem that requires fast existence checks.
2. Scanning for the missing element
Once you have the set, you scan through a second collection to find the value that is absent:
for a, b in paths:
if b not in sources:
return b
This "find the outlier" scan is a building block that appears in many forms. Sometimes you are looking for the number not in a set. Sometimes you are looking for the first character that has frequency 1. The structure is always the same: build a reference collection, then scan for the element that breaks the pattern.
Edge cases
- Single path:
[["A", "B"]]. The source set is{"A"}. City"B"is not in the set. Returns"B"correctly. The minimum valid input. - Long chain: a chain of 100 cities. The source set has 99 entries. The last city in the chain never appears as a source. The second loop finds it and returns immediately.
- Cities with similar names:
[["AB", "ABC"], ["ABC", "ABCD"]]. String comparison is exact."ABCD"is not in the source set{"AB", "ABC"}. No risk of partial matching. - Single-character city names:
[["a", "b"], ["b", "c"]]. Works the same way. The set contains{"a", "b"}, and"c"is the answer.
From understanding to recall
You have seen how a single set and two passes solve this problem. The logic is minimal. But under interview pressure, the small details matter. Do you add the left element or the right element to the set? Do you check b not in sources or a not in sources? These feel obvious when you are reading a solution, but reproducing them from memory is different.
Spaced repetition closes that gap. You practice writing the set-building loop and the membership-check scan from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "find the element that never appears in one position" and the set approach flows out without hesitation.
Related posts
- Find the Town Judge - Another problem where you identify a node with a unique property by counting or collecting relationships
- Course Schedule - Uses in-degree counting in a directed graph, the next level of complexity after simple set membership
- Happy Number - Uses a set to detect cycles in a sequence, another application of the "have I seen this before?" pattern
CodeBricks breaks Destination City into its set-building and membership-scanning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a set-based lookup problem shows up in your interview, you do not hesitate. You just write it.