Reconstruct Itinerary — The Ticket Shoebox · DSA Quest

1Reconstruct Itinerary — The Ticket Shoebox

2Min Cost to Connect All Points — The Village Power Grid

3Network Delay Time — The Telegraph Network

Boss 1: The Ticket Shoebox

Dungeon 14 closed with a promise: Dijkstra is just greedy with a priority queue. That boss is real and it's coming. But every dungeon opens with a gatekeeper, and this one hands you a weapon you already own — plain DFS from Dungeon 11 — then changes one word in the manual.

Every graph quest so far visited nodes. Mark a room seen, never enter it twice. This boss doesn't care how many times you pass through a room. It cares that you use every door exactly once. First time in the whole quest that the thing being consumed is the edge, not the node. That one word breaks your old DFS in a way that's genuinely fun to watch.

The story

Your uncle flew packages for a living. He died mid-route somewhere over the Pacific, and the airline can't close his expense file until someone reconstructs his final trip.

Clearing out his flat, you find it: a shoebox of used ticket stubs. Each stub says only from and to. No dates, no times, no order.

JFK → KUL     JFK → NRT     NRT → JFK

You know two things for certain. The trip started at JFK, and he flew every ticket in the box exactly once — couriers don't buy tickets they don't use. The airline adds a third rule, because bureaucracies love ties: if more than one ordering of the stubs makes a valid trip, file the one that reads alphabetically smallest.

Three stubs is easy. His real shoebox has three hundred, and half of them revisit the same airports.

The problem, dressed up properly

You are given a list of airline tickets where tickets[i] = [from, to]. Reconstruct the itinerary in order and return it. All tickets begin from "JFK". If multiple valid itineraries exist, return the one with the smallest lexical order. You must use all tickets exactly once. At least one valid itinerary is guaranteed to exist.

LeetCode 332, "Reconstruct Itinerary". Hard-rated for years, now medium, and the cleanest possible introduction to Eulerian paths — a path that walks every edge of a graph exactly once.

The naive attempt

The obvious plan: at every airport, try the alphabetically smallest unused ticket first. If that choice eventually strands you with tickets left over, undo it and try the next one. Backtracking.

from collections import defaultdict
 
def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets):
        graph[src].append(dst)      # each list is sorted, smallest first
 
    n = len(tickets)
    route = ["JFK"]
 
    def backtrack(airport):
        if len(route) == n + 1:     # every ticket flown
            return True
        dests = graph[airport]
        for i in range(len(dests)):
            nxt = dests.pop(i)      # try this ticket
            route.append(nxt)
            if backtrack(nxt):
                return True
            route.pop()             # dead end: un-fly it
            dests.insert(i, nxt)
        return False
 
    backtrack("JFK")
    return route

This is correct. Trying smallest-first means the first complete route it finds is the lexical winner. On LeetCode's real tests it even passes.

But look at what it's doing. Every wrong turn is undone ticket by ticket, and a nasty graph can make it commit to a long, almost-right prefix before discovering the mistake — then unwind hundreds of flights and try again one ticket over. Worst case, that's exponential. The shoebox deserves better than "retry the whole trip".

And here's the thing the backtracking is quietly hiding: the problem guarantees a valid itinerary exists. When an Eulerian path is guaranteed, you shouldn't need to undo anything. There should be a way to walk once and win.

The weapon: get stuck on purpose

First, feel the trap. Tickets: JFK → KUL, JFK → NRT, NRT → JFK. Greedy says: from JFK, fly to KUL — it beats NRT alphabetically. You land in KUL. KUL has no outgoing tickets. Two stubs still in the box. Stranded.

The correct route is JFK → NRT → JFK → KUL. Greedy wasn't wrong that KUL comes cheap. It was wrong about when. KUL is a dead end, and dead ends belong at the end of the route, not wherever greedy happens to meet them.

Hierholzer's algorithm turns that observation into the whole solution:

Sort each airport's destinations alphabetically.
DFS from JFK, always flying the smallest remaining ticket, consuming it as you go. No undo.
When an airport has no tickets left — you're stuck — that's when you append it to the route.
When the dust settles, reverse the route.

Why does this work? When you get stuck, the airport you're stuck at must be the true final stop of some suffix of the journey — there's no ticket out of it, so nothing can come after it. Recording airports at stuck-time builds the route back-to-front. Any leftover tickets at airports you backtrack through are little side loops, and the recursion splices them in at exactly the right place, because a loop's airports only get recorded after everything beyond them is done.

from collections import defaultdict
 
def find_itinerary(tickets: list[list[str]]) -> list[str]:
    graph: dict[str, list[str]] = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)          # reverse-sorted, so pop() gives smallest
 
    route: list[str] = []
 
    def visit(airport: str) -> None:
        stops = graph[airport]
        while stops:
            visit(stops.pop())          # consume the smallest ticket, O(1)
        route.append(airport)           # record only when stuck (post-order)
 
    visit("JFK")
    return route[::-1]

No visited set. No undo. Every ticket is popped exactly once, forever. The sort in reverse order is a small pro move: the smallest destination sits at the end of each list, so pop() grabs it in O(1) instead of pop(0) shifting the whole list.

Watching it work

The trap graph, since it's the honest test. Adjacency after the reverse sort: JFK holds [NRT, KUL] (so pop() yields KUL first), NRT holds [JFK].

visit(JFK)   pop KUL  → visit(KUL)
visit(KUL)   no tickets            → route = [KUL]
             back in JFK, pop NRT  → visit(NRT)
visit(NRT)   pop JFK   → visit(JFK)
visit(JFK)   no tickets left       → route = [KUL, JFK]
             back in NRT, empty    → route = [KUL, JFK, NRT]
             back in JFK, empty    → route = [KUL, JFK, NRT, JFK]

reverse → [JFK, NRT, JFK, KUL]  ✓

The exact walk that stranded the greedy version happens here too — we did fly to KUL first. But getting stuck wasn't failure, it was information: KUL can only be last, so it's recorded first and the reversal buries it at the tail. The NRT loop we skipped gets spliced in on the way back, no undo required.

Post-order is a time machine

Appending on the way back instead of the way in shows up everywhere: topological sort records a node after all its dependencies, tree deletion frees children before parents, and Hierholzer records an airport after every trip beyond it is settled. When "this thing can only come after everything it leads to", build the answer backwards and reverse once. It converts an exponential search into a single walk.

Gotchas

1. Appending on arrival instead of on stuck. Move route.append(airport) above the while loop and you've rebuilt the naive greedy — it files KUL in position two and strands the trip. The entire algorithm lives in that one line being after the loop. Post-order or nothing.

2. Forgetting the final reverse. The route is constructed back-to-front. Return it raw and the trap example hands the airline [KUL, JFK, NRT, JFK], a trip that starts at an airport with no tickets. route[::-1], always.

3. Storing destinations in a set. Real shoeboxes have duplicate tickets — he flew ATL → JFK twice. A set silently merges them and you finish with tickets unspent. The destination list is a multiset: keep the list, pop one copy per flight.

4. Sorting ascending and popping from the front. sorted(tickets) plus pop(0) is correct but each pop shifts the rest of the list, O(V) per ticket, O(E · V) overall. Sort with reverse=True and pop() from the tail for O(1), or use a heap per airport if you'd rather not think about it.

Complexity

Sorting the tickets dominates. The walk itself touches every ticket exactly once.

Time: O(E log E). Space: O(E) for the adjacency lists and the recursion stack (the route can revisit airports, so the stack is bounded by tickets, not airports).

Boss down

The itinerary lands on the airline's desk, alphabetically immaculate, and your uncle's file finally closes. The gatekeeper falls to a weapon from four dungeons ago with a single word changed: consume edges, not nodes, and record on the way out, not the way in.

Keep the shoebox reflex — "a path that uses every edge exactly once" is an Eulerian path, and Hierholzer solves it in linear time wherever it appears: DNA fragment assembly, snow-plow routing, that old puzzle about drawing a figure without lifting the pen.

Next boss: Min Cost to Connect All Points — The Village Power Grid. A valley of scattered houses, one budget, and every home must reach the grid. That's a minimum spanning tree, Prim's algorithm is the weapon, and the heap you forged in Dungeon 10 comes off the wall — its first swing in the direction Dungeon 14's finale promised. See you at the substation.