Skip to content

Volume ITechnology

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, so here it is 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.

A picture to hold in mind ​

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.

The solution ​

python
from collections import defaultdict

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

Line by line ​

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

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.

Edge cases ​

  • One ticket. The route is JFK and its one destination.
  • The smallest choice leads into a dead end, as in the second example. Line (8) still places the dead end last, so the route is correct.
  • Two tickets for the same flight. Both are in the list and both are used, one at a time.

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 ​

This is the natural follow-up question, so be ready for it.

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

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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet