Given a list of airline tickets [from, to], reconstruct the itinerary. It must start at "JFK", use every ticket exactly once, and when several itineraries are possible, return the one that is smallest in lexical order.
"Use every edge exactly once" is an Eulerian path, not a normal traversal. Every other graph problem in this book visits every node; this one visits every edge.
And plain greedy fails. If you always take the smallest available destination, you can strand yourself: you reach an airport with no tickets left while tickets remain elsewhere. The second example does exactly this if you greedily take ATL → JFK at the wrong moment.
So you need an algorithm that is greedy and recovers from dead ends.
Imagine a museum with a very strict guided tour rule: you must walk through every single hallway exactly once. You start at the lobby (JFK). Since you don't have a map, you just guess which hallway to take. If you hit a dead end room (where you've already walked all hallways leaving it), you know you must be at the very end of the entire tour! Why? Because if it wasn't the end, you'd be trapped. So you write down that room's name as the FINAL stop, and you hit "undo" to walk backwards to the previous room, looking for any other hallways you skipped. You keep doing this, recording rooms as they run out of options. In the end, the list you wrote down is perfectly backwards, so you flip it around.
Why is that true? In a graph that has an Eulerian path, only one node can have no outgoing edge left — the final destination. So getting stuck is not a failure; it is arriving at the end.
Backing up and continuing means any tickets you skipped get used on the way back, and each gets added to the answer before the stuck node, which is where they belong.
The answer comes out backwards — you record the end first — so reverse it at the finish.
Sort each airport's destinations so that the greedy step always takes the lexically smallest available. Combined with the recovery, that produces the smallest valid itinerary.
from collections import defaultdictclass Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: adj = defaultdict(list) # (1) for src, dst in sorted(tickets, reverse=True): # (2) adj[src].append(dst) # reverse-sorted, so pop() gives the smallest route = [] # (3) def visit(airport: str): # (4) while adj[airport]: # (5) nxt = adj[airport].pop() # (6) smallest remaining destination visit(nxt) # (7) route.append(airport) # (8) no tickets left → this is an endpoint visit("JFK") # (9) return route[::-1] # (10)
ts
function findItinerary(tickets: string[][]): string[] { const adj = new Map<string, string[]>(); // (1) const sorted = [...tickets].sort((a, b) => b[1].localeCompare(a[1])); // (2) for (const [src, dst] of sorted) { if (!adj.has(src)) adj.set(src, []); adj.get(src)!.push(dst); } const route: string[] = []; // (3) function visit(airport: string): void { // (4) const dests = adj.get(airport); while (dests && dests.length) { // (5) visit(dests.pop()!); // (6) } route.push(airport); // (8) } visit("JFK"); // (9) return route.reverse(); // (10)}
Three things carry the solution.
Sorting in reverse so that pop() takes the smallest. Popping from the end of a list is O(1); removing from the front is O(n). Reversing the sort order lets you have both cheapness and lexical order.
Removing the ticket as you use it is what enforces "each ticket exactly once". The destination list is the set of unused tickets.
route.append(airport) happens after the while loop — that is, after every ticket out of this airport has been used. This is the post-order position, and it is the entire algorithm. An airport is added when it is finished, so the finishing order is the route reversed.
(1) For each airport, the list of places you hold a ticket to from there.
(2) Add the tickets in reverse alphabetical order. The problem wants the alphabetically smallest itinerary when there is a choice. Storing each list biggest-first means pop(), which takes from the end, always hands back the smallest remaining destination, in constant time.
(3) The route, built backwards. See line (8).
(4) visit(airport) uses up every ticket reachable from here.
(5) While this airport still has unused tickets out of it,
(6) take the alphabetically smallest one and remove it, so it is never used twice,
(7) and fly there, using up its tickets in turn.
(8) No tickets are left out of this airport, so it is the end of everything that follows it. We add it to the route only now, once all its onward flights are done. So the route is built from the end of the trip back toward the start. This late adding is what makes the algorithm work even when the smallest choice leads into a dead end: the dead end is added first, so it ends up at the very end of the trip, where it belongs.
(9) Every trip starts at JFK.
(10) Reverse the route, so it reads from start to finish.
You could backtrack: try each destination, and undo the ticket if the branch fails to use everything. That works and it is exponential in the worst case, because a wrong first choice may be discovered only after exploring a huge subtree.
Hierholzer's is O(E \log E) — dominated by the sort — because no choice is ever wrong. Getting stuck is not a failure to be undone; it is information about where the route ends.
Cracking the Safe (LeetCode 753) — build a De Bruijn sequence, which is an Eulerian circuit on a graph of prefixes. The connection is not obvious, which is why it is listed here.
Valid Arrangement of Pairs — the same algorithm without the fixed start, so you must first work out where the path begins from the degree imbalance.
The Seven Bridges of Königsberg — Euler's 1736 paper on exactly this question is the origin of graph theory. He proved no such walk existed because four nodes had odd degree.
"Why does greedy alone fail?" You can strand yourself at a dead end with tickets still unused. Give the second example.
"Why is getting stuck not a failure?" Only the final destination can run out of edges, so the stuck node is the end of the route.
"Why is the answer reversed?" Nodes are recorded when they finish, and the last one to be reachable finishes first.
"How do you get lexical order?" Sort each destination list and always take the smallest available.
"Why sort in reverse?" So pop() from the end is O(1) and still yields the smallest.
"Is this a Hamiltonian path?" No — Hamiltonian visits every node once and is NP-hard. Eulerian visits every edge once and is linear. That contrast is the single best thing to volunteer here, because it shows you know why this problem is tractable at all.