4.21.1 — Reconstruct Itinerary

LeetCode 332 · Hard

The problem

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.

tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
→ ["JFK","MUC","LHR","SFO","SJC"]

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
→ ["JFK","ATL","JFK","SFO","ATL","SFO"]

A valid itinerary is guaranteed to exist.

What makes this hard

"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.

Hierholzer's algorithm

The idea is unusual and worth stating carefully:

Walk greedily until you get stuck. The airport you got stuck at must be the end of the route. Add it to the answer, back up, and continue from there.

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.

The solution

Python

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        adj = defaultdict(list)
        for src, dst in sorted(tickets, reverse=True):
            adj[src].append(dst)          # reverse-sorted, so pop() gives the smallest

        route = []

        def visit(airport: str):
            while adj[airport]:
                nxt = adj[airport].pop()  # smallest remaining destination
                visit(nxt)
            route.append(airport)         # no tickets left → this is an endpoint

        visit("JFK")
        return route[::-1]

TypeScript

function findItinerary(tickets: string[][]): string[] {
  const adj = new Map<string, string[]>();
  const sorted = [...tickets].sort((a, b) => b[1].localeCompare(a[1]));
  for (const [src, dst] of sorted) {
    if (!adj.has(src)) adj.set(src, []);
    adj.get(src)!.push(dst);
  }

  const route: string[] = [];

  function visit(airport: string): void {
    const dests = adj.get(airport);
    while (dests && dests.length) {
      visit(dests.pop()!);
    }
    route.push(airport);
  }

  visit("JFK");
  return route.reverse();
}

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.

Trace on the second example

Tickets from JFK: [ATL, SFO]; from ATL: [JFK, SFO]; from SFO: [ATL].

Start at JFK, take ATL. From ATL take JFK. From JFK take SFO. From SFO take ATL. From ATL take SFO. SFO now has no tickets left → append SFO.

Unwind: ATL has none left → append ATL. SFO none → append SFO. JFK none → append JFK. ATL none → append ATL. JFK none → append JFK.

route = [SFO, ATL, SFO, JFK, ATL, JFK], reversed → [JFK, ATL, JFK, SFO, ATL, SFO] ✓

Notice how the first dead end (SFO) became the last stop, and everything else filled in around it as the recursion unwound.

Why the naive backtracking is worse

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.

That reframing is the thing to take away.

Complexity

O(E \log E) time, from sorting the tickets. The traversal itself is O(E), since each edge is used exactly once.

O(E) space.

When an Eulerian path exists

Worth knowing, because it is the natural follow-up.

For a directed graph, an Eulerian path exists when the graph is connected (ignoring isolated nodes) and either:

• every node has equal in-degree and out-degree — then it is an Eulerian circuit, and you may start anywhere; or
• exactly one node has out − in = 1 (the start) and exactly one has in − out = 1 (the end), and all others are balanced.

This problem guarantees a solution exists, so you never check. In a real implementation you would.

Where this goes next

• 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 and is worth knowing.
• 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.

What the interviewer will push on

"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.

Next: 4.21.2 Min Cost to Connect All Points — the first weighted graph, and the minimum spanning tree.