Reconstruct Itinerary
Understanding the Problem
This problem is 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." When multiple valid paths exist, we return the one that is smallest when read as a single string.
This is not a standard DFS over nodes. We need to traverse every edge exactly once, which means we may visit the same airport multiple times. In Example 2, JFK, ATL, and SFO are each visited twice. Traversing every edge exactly once is the defining condition of an Eulerian path, and Hierholzer's algorithm is the standard method for constructing one.
Key Constraints:
1 <= tickets.length <= 300→ With at most 300 edges, an O(E log E) traversal is well within limits, and a backtracking solution that explores a few dead ends still runs fast.from_i.length == 3,to_i.length == 3→ Airport codes are always 3 uppercase letters, so string comparisons take constant time.- "All tickets form at least one valid itinerary" → An Eulerian path is guaranteed to exist, so the algorithm needs no existence check.
- "Must use all tickets exactly once" → Identical routes can appear more than once, so we track the count of remaining tickets per route rather than a single boolean per edge.
Approach 1: DFS with Backtracking
Intuition
Build a graph from the tickets, sort each airport's destinations lexicographically, then do a DFS from "JFK," trying to use all tickets. If a branch reaches a dead end before all tickets are used, backtrack and try the next destination at the most recent choice point.
Sorting the destinations means that at every airport we attempt the lexicographically smallest option first. The first complete path we find (one that uses all tickets) is therefore the smallest valid itinerary, so we can return as soon as we find it.
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.
Backtracking can revisit many partial paths before finding the answer. The next approach builds the itinerary in a single traversal, with no undoing.
Approach 2: Hierholzer's Algorithm (Optimal)
Intuition
Hierholzer's algorithm constructs an Eulerian path without backtracking. Do a DFS, always visiting the lexicographically smallest unused neighbor. When an airport has no more outgoing tickets, add it to the front of the result and return to its caller.
Building the path in reverse works because of what a dead end represents. When the DFS gets stuck at an airport with no remaining tickets, every edge out of that airport has already been consumed, so that airport must come last among all the nodes still on the current call stack. Adding dead ends to the front places the tail of the path first, and the rest of the path fills in ahead of it as each recursive call returns.
Pre-order insertion (recording each airport when first visited) breaks on graphs where the greedy smallest choice leads into a branch that returns to the start before other edges are covered. The visit order would then list airports that cannot connect into one path. Post-order insertion avoids this: a node is recorded only once all of its outgoing edges are spent, so the recorded order, reversed, is always a single valid Eulerian path.
Lexicographic minimality comes from the min-heap. At each airport the smallest available destination is taken first, so among all valid Eulerian paths the one produced is the smallest.
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.