Reconstruct Itinerary
Use every flight ticket exactly once, starting from JFK, and return the alphabetically smallest itinerary: an Eulerian path found with Hierholzer's algorithm.
Problem Understanding
Reconstruct Itinerary: given flight tickets [from, to], use every ticket exactly once to build a trip starting at "JFK". If several trips are possible, return the one that is smallest in alphabetical order.
Examples: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] returns ["JFK","MUC","LHR","SFO","SJC"]; [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] returns ["JFK","ATL","JFK","SFO","ATL","SFO"].
The Intuition: Dead Ends Go Last
Using every ticket once means walking every directed edge once, an Eulerian path:
- Fly the smallest ticket first, because the answer must be alphabetically smallest.
- A stuck airport is not a failure. If the airport on top of the stack has no tickets left, every other ticket must be used before reaching it, so it belongs at the end of the trip. Pop it onto the route.
- Pop order is the trip backwards. Reverse the route at the end.
That is Hierholzer's algorithm, a depth-first search where nodes are recorded as they finish, the same post-order idea that Topological Sort uses. Course Schedule and Alien Dictionary are other directed-graph problems in the graphs pattern.
Interactive Walkthrough
GREEN ARROW = TICKET USED
SORT DESTINATIONS
stack
Empty
route (reversed)
Nothing popped yet
Group tickets by origin, destinations in alphabetical order: ATL → JFK, SFO; JFK → ATL, SFO; SFO → ATL
Next
Start the stack at JFK
tickets
Airports are nodes and tickets are arrows; a used ticket turns green. The airport on top of the stack is solid, the rest of the stack is tinted, and airports already popped onto the route are green. Try Dead end to see the alphabetically first airport end up last.
Dry Run Table
Input: JFK→KUL, JFK→NRT, NRT→JFK. Sorted destinations: JFK: [KUL, NRT], NRT: [JFK].
| Stack | Top's tickets left | Action | Route (popped) |
|---|---|---|---|
| JFK | KUL, NRT | fly to KUL | |
| JFK, KUL | none | pop KUL | KUL |
| JFK | NRT | fly to NRT | KUL |
| JFK, NRT | JFK | fly to JFK | KUL |
| JFK, NRT, JFK | none | pop JFK | KUL, JFK |
| JFK, NRT | none | pop NRT | KUL, JFK, NRT |
| JFK | none | pop JFK | KUL, JFK, NRT, JFK |
Answer: reversed, JFK → NRT → JFK → KUL.
The Solution Template
Destinations kept sorted (a reverse-sorted list popped from the end, a priority queue, or a multiset), one stack, and a route reversed at the end.
Reconstruct Itinerary Code
1var findItinerary = function(tickets) {2 const graph = new Map();3 for (const [src, dst] of [...tickets].sort((a, b) => (a[0] + a[1] < b[0] + b[1] ? 1 : -1))) {4 if (!graph.has(src)) graph.set(src, []);5 graph.get(src).push(dst);6 }7 const route = [], stack = ['JFK'];8 while (stack.length) {9 const next = graph.get(stack[stack.length - 1]);10 if (next && next.length) stack.push(next.pop());11 else route.push(stack.pop());12 }13 return route.reverse();14};
Edge Cases & Common Mistakes
- Greedy without backing up: flying the smallest ticket and stopping at a dead end misses tickets; pop dead ends onto the route instead.
- Duplicate tickets: the same route can appear twice; keep both (a list or multiset, not a set).
- Forgetting to reverse: airports are popped in reverse trip order.
- Sorting the wrong way for pop(): with a list popped from the end, sort destinations in reverse so the smallest comes off first.
- Recursion depth: a recursive DFS goes one level per ticket; the iterative stack avoids deep recursion.
Summary
Sort each airport's destinations. From a stack starting at JFK, fly the smallest unused ticket while the top has one; otherwise pop the top onto the route. Reverse the route. O(E log E) time for sorting, O(E) space.
More practice: DSA interview questions with answers · patterns cheat sheet