Reconstruct Itinerary (LeetCode 332)

The problem

You get a list of airline tickets [from, to]. Build the itinerary that starts at "JFK" and uses every ticket exactly once. If several itineraries are possible, return the one that is smallest in lexical order when read as a single sequence. A valid itinerary is guaranteed to exist.

Input:  tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

From JFK the only ticket goes to MUC, then LHR, then SFO, then SJC. Every ticket is used once.

How to think about it

Start with brute force. Backtracking: from the current airport, try destinations in sorted order, mark the ticket used, and recurse. Undo on a dead end. The first complete route found is the answer. It works, but in the worst case it backtracks a lot.

The key insight: this is an Eulerian path. Airports are nodes and tickets are directed edges. “Use every edge exactly once” is the definition of an Eulerian path, and Hierholzer’s algorithm finds one in linear time without backtracking.

How Hierholzer’s works. Walk greedily from the start, always taking an unused edge, until you get stuck at a node with no edges left. A stuck node must be the end of the remaining route, so you append it to the route and back up one step. From there, continue walking any edges still unused. Each time you get stuck, you append. The route is built backwards, so reverse it at the end. Dead ends get pushed to the end of the itinerary automatically, which is exactly where they belong.

Getting lexical order. Always take the smallest destination first. Sort the tickets in reverse and push them onto per-airport lists, so pop() from the end returns the smallest destination in O(1).

Which pattern is this? Eulerian path. The tell is “use every edge exactly once”.

Approach

1. Sort tickets in reverse and build adj[from] lists, so the smallest destination sits at the end of each list.
2. Start a stack with "JFK".
3. While the airport on top of the stack still has tickets, pop its smallest destination and push it onto the stack.
4. When the top airport has no tickets left, pop it and append it to route.
5. Repeat until the stack is empty, then return route reversed.

Solution

from collections import defaultdict
def findItinerary(tickets):
    adj = defaultdict(list)
    for a, b in sorted(tickets, reverse=True): adj[a].append(b)   # smallest dest at the end
    route = []; stack = ["JFK"]
    while stack:
        while adj[stack[-1]]: stack.append(adj[stack[-1]].pop())  # walk until stuck
        route.append(stack.pop())                                 # stuck node ends the remaining route
    return route[::-1]
# findItinerary([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]) -> ["JFK","MUC","LHR","SFO","SJC"]

Dry run

On the example, the walk never branches:

Reversed: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

The interesting case is a dead end. With [["JFK","KUL"], ["JFK","NRT"], ["NRT","JFK"]], the greedy walk goes JFK → KUL first (KUL < NRT) and gets stuck. KUL is appended first, so it ends up last. The walk then resumes JFK → NRT → JFK, and the answer is ["JFK", "NRT", "JFK", "KUL"].

Complexity

• Time: O(E log E). Sorting the tickets dominates; the walk pushes and pops each ticket once.
• Space: O(E). The adjacency lists, the stack and the route.

Edge cases and pitfalls

• Dead ends: greedily taking the smallest airport and returning the walk directly (without the post-order trick) fails on the KUL example above.
• Duplicate tickets (the same flight twice) are separate edges; lists handle them, sets would not.
• Forgetting to reverse the route returns the itinerary backwards.
• Sorting ascending and popping from the front of a list is O(n) per pop. Sort in reverse and pop from the end, or use a heap.
• Recursive DFS works too but can hit the recursion limit on long itineraries.

Related problems

• Alien Dictionary (LeetCode 269): another “find an order” problem on a directed graph, using topological sort.
• Course Schedule II (LeetCode 210): ordering nodes rather than edges.
• Critical Connections in a Network (LeetCode 1192): another named DFS algorithm (Tarjan’s) that you need to recognise on sight.