Skip to content

#1436EasyHashmap

Destination City

View on LeetCode ↗

Start dumb: chase the chain

The paths form a line of cities, so you could pick any start, follow its outgoing path to the next city, follow that one’s path, and keep going until you hit a city with nowhere to go. That works, but it means a lookup per hop and code that has to find each city’s outgoing edge — fiddly, and easy to get wrong when the paths are listed out of order.

Find the bottleneck

Step back from the chain. What actually defines the destination? It is the one city that is reached by a path but starts none. “Starts a path” is the whole test — and it’s a property you can precompute for every city in one sweep, regardless of the order the paths are listed in.

The optimal shape

  1. Pass one: add every path[0] to a sources set.
  2. Pass two: return the first path[1] that is not in sources.

In the player, phase one lights up each path as its start city is filed; phase two walks the landing cities, ruling out every one that also appears as a source until the single gap remains — the destination.

Watch it think

Run the default (a tidy in-order chain), then the traps: a shuffled list where the destination sits in the middle (A,B; B,C; D,A), the same chain listed backwards so the answer is the first path’s target (C,D; B,C; A,B), and the one-path base case (A,Z).

Re-traces as you type — paths as "from,to" pairs split by ';' — e.g. "London,New York; New York,Lima; Lima,Sao Paulo"; up to 8 paths, names up to 14 chars. Capped at 32 characters so the tiles stay readable.

Trap inputs:

Step 1 of 7: The destination is reached by a path but starts none, so first collect every city that DOES start a path — the answer is the one landing city missing from that set. Variables: sources = {}.

Data

Code

1fun destCity(paths: List<List<String>>): String {
2    val sources = HashSet<String>()
3    for (p in paths) {
4        sources.add(p[0])
5    }
6    for (p in paths) {
7        if (p[1] !in sources) return p[1]
8    }
9    return ""
10}

State

sources
{}

Why this step

The destination is reached by a path but starts none, so first collect every city that DOES start a path — the answer is the one landing city missing from that set.

1 / 7

The same pattern also solves

Recognize the window, and these fall to the same skeleton.