Reconstruct Itinerary
Last Updated: March 28, 2026
Understanding the Problem
This problem is really about finding an Eulerian path in a directed graph. Each ticket is a directed edge from one airport to another, and we need to traverse every edge exactly once, starting from "JFK." The twist is the lexicographic ordering requirement: when multiple valid paths exist, we need the one that's smallest when read as a string.
The key observation is that this isn't a standard DFS where we just visit nodes. We need to visit every edge exactly once. That distinction matters because we might visit the same airport multiple times (as in Example 2, where JFK, ATL, and SFO are all visited twice). This is exactly the setup for Hierholzer's algorithm, which finds Eulerian paths in graphs.
Key Constraints:
1 <= tickets.length <= 300→ With at most 300 edges, even O(n^2) approaches are fine. But the graph structure suggests DFS-based solutions are natural.from_i.length == 3,to_i.length == 3→ Airport codes are always 3 uppercase letters, so string comparisons are constant time.- "All tickets form at least one valid itinerary" → We're guaranteed an Eulerian path exists. No need to check for existence.
- "Must use all tickets exactly once" → This is the Eulerian path condition: traverse every edge exactly once.
Approach 1: DFS with Backtracking
Intuition
The most direct way to think about this: build a graph from the tickets, sort each airport's destinations lexicographically, and then do a DFS from "JFK," trying to use all tickets. If we hit a dead end before using all tickets, we backtrack and try the next destination.
This approach is correct because sorting guarantees we try the lexicographically smallest path first. The first complete path we find (one that uses all tickets) is our answer, so we can stop immediately.
Algorithm
- Build an adjacency list from the tickets. For each departure airport, store a sorted list of destination airports.
- Track which tickets have been used (since the same route can appear multiple times, we track ticket usage, not just edge existence).
- Start DFS from "JFK." At each airport, try destinations in sorted order.
- For each destination, mark the ticket as used and recurse. If the recursion uses all tickets, we've found our answer.
- If not, unmark the ticket (backtrack) and try the next destination.
Example Walkthrough
Code
- Time Complexity: O(E!) in the worst case, where E is the number of tickets. Backtracking can explore many permutations of edge orderings. In practice, sorted order and early termination make this much faster.
- Space Complexity: O(V + E). The adjacency list stores all edges, and the recursion stack can go up to E levels deep. V is the number of unique airports.
This approach works correctly but can be slow due to backtracking. What if there was a way to build the path in a single traversal, without ever needing to undo work?
Approach 2: Hierholzer's Algorithm (Optimal)
Intuition
Hierholzer's algorithm is the elegant solution to Eulerian path problems. The idea is beautifully simple: do a DFS, always visiting the lexicographically smallest unused neighbor. When you reach a dead end (a node with no more outgoing edges), add that node to the front of the result and backtrack.
Why does building the path in reverse work? Consider what happens at a dead end. If we're stuck at some airport with no more tickets, it means all edges leading out of that airport have been used. In an Eulerian path, the last node in the path must be a dead end. By adding dead-end nodes to the front, we're effectively placing the "tail" of our path first, then filling in the rest as we backtrack.
The post-order insertion is the magic. In a regular DFS, if we added nodes in pre-order (as we visit them), a greedy lexicographic choice could lead us down a dead-end branch too early, skipping edges we need to traverse first. Post-order fixes this: dead ends are placed last (at the front of the reversed result), and the rest of the path fills in correctly as we backtrack.
The min-heap guarantees that at every step, we choose the lexicographically smallest available destination. Combined with the post-order insertion, this produces the globally smallest valid itinerary.
Algorithm
- Build an adjacency list where each airport maps to a min-heap (priority queue) of its destinations.
- Start DFS from "JFK."
- At each airport, while there are unused outgoing tickets, pop the smallest destination and recurse.
- When no more outgoing tickets remain (dead end), add the current airport to the front of the result.
- The final result is the Eulerian path in the correct order.
Example Walkthrough
Code
- Time Complexity: O(E log E). Building the graph takes O(E). Each edge is inserted into and removed from a min-heap once, which is O(log E) per operation. Total: O(E log E), where E is the number of tickets.
- Space Complexity: O(V + E). The adjacency list stores all edges (O(E)), and the recursion stack can go up to E levels deep. V is the number of unique airports.