Leetcode 332. Reconstruct Itinerary

Let's understand what we're being asked to do. We have a list of flight tickets like [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]], where each ticket is [from, to]. We must start at "JFK" and use every ticket exactly once to build an itinerary.

Tracing through: Starting at "JFK", we could go to "SFO" or "ATL". If multiple valid itineraries exist, we need the lexicographically smallest one (alphabetically first). So if we can go to "ATL" or "SFO", we should choose "ATL" because it comes first alphabetically.

Important constraint: We must use every ticket exactly once. This means we're finding a path through a graph that visits every edge exactly once (an Eulerian path).

Edge cases to consider: What if there's no valid itinerary? (The problem guarantees at least one exists). What if we have multiple tickets between the same two airports? What if we reach a dead end and need to backtrack?

This is about finding an Eulerian path in a directed graph - a path that uses every edge exactly once. The key insight is that we should explore destinations in lexicographical order (alphabetically), but we might need to backtrack if we hit a dead end.

If we greedily always pick the alphabetically smallest next destination, we might get stuck. For example, from "JFK" we might go to "AAA" first (alphabetically smallest), but that could be a dead end, forcing us to backtrack and try "BBB" instead.

A naive greedy approach (always pick smallest destination) fails because it doesn't account for dead ends. We need a strategy that explores in lexicographical order but can undo choices when we get stuck.

This is why we need to process destinations in sorted order AND use a technique that naturally supports backtracking - building the path in reverse as we return from dead ends.

Think of planning a road trip where you must use every highway segment exactly once. You want to visit cities alphabetically when possible, but some routes lead to dead ends.

Imagine you reach a city with no outgoing roads - you're stuck! You need to record this city as the end of your path, then backtrack to the previous city and try a different route. By building the path backwards (recording cities as you finish exploring them), you naturally handle dead ends and backtracking.

Build an adjacency list where each airport maps to a sorted list of destinations (for lexicographical order). Use DFS with backtracking: recursively visit destinations, removing used tickets as we go. When we reach a dead end (no more outgoing flights), add that airport to the result. Build the itinerary in reverse order by adding airports as we backtrack, then reverse the final result. This Hierholzer's algorithm variation naturally handles Eulerian paths with lexicographical ordering.

from collections import defaultdict
def find_itinerary(tickets):
    """
    Reconstruct flight itinerary using Hierholzer's algorithm for Eulerian path.
    Uses DFS with lexicographical ordering to find the smallest valid itinerary.
    """
    # Build adjacency list with sorted destinations for lexicographical order
    graph = defaultdict(list)
    
    for src, dst in tickets:
        graph[src].append(dst)
    
    # Sort destinations for each airport to ensure lexicographical order
    for src in graph:
        graph[src].sort(reverse=True)
    
    # Result will be built in reverse order
    itinerary = []
    
    def dfs(airport):
        # Visit all destinations from current airport
        while graph[airport]:
            # Pop from end (smallest due to reverse sort)
            next_dest = graph[airport].pop()
            dfs(next_dest)
        # Add to itinerary when no more outgoing flights (backtracking)
        itinerary.append(airport)
    
    # Start DFS from JFK
    dfs("JFK")
    
    # Reverse to get correct order (we built it backwards)
    return itinerary[::-1]

• Eulerian path with Hierholzer's algorithm: When a problem requires visiting every edge exactly once in a directed graph, recognize it as an Eulerian path problem - use post-order DFS traversal where you add nodes to the result *after* exploring all outgoing edges, then reverse the result to get the correct path order.
• Lexicographic ordering with sorted adjacency lists: Store destinations in a min-heap or sorted list for each source airport, and always pop the smallest unvisited destination first - this ensures the lexicographically smallest valid path without needing to generate and compare all possible itineraries.
• Graph representation for edge consumption: Use an adjacency list with removable edges (like a list you can pop from, or a multiset) rather than marking edges as visited - this naturally handles multiple tickets between the same airports and prevents reusing tickets.
• Post-order traversal insight: The counterintuitive key is building the itinerary in reverse order - you explore dead-ends first and backtrack, adding airports to the result only after exhausting all their outgoing flights, which guarantees you don't get stuck with unused tickets.
• Dead-end handling pattern: Unlike standard DFS, Hierholzer's algorithm gracefully handles nodes with no outgoing edges by placing them at the end of the path segment - this is why recursive backtracking with post-order insertion works perfectly for Eulerian paths where some nodes are dead-ends.
• Real-world route optimization: This technique applies to any scenario requiring traversal of all connections exactly once - GPS route planning with mandatory road segments, mail delivery routes, circuit board trace routing, or DNA sequence assembly where fragments must be used exactly once to reconstruct the genome.