Domain 2MediumCORE

Reconstruct Itinerary

We need to reconstruct an itinerary from a set of airline tickets. The core constraints define the problem structure: 1. Start Node: Must begin at 'JFK'. 2. Edge Usage: Every ticket (directed edge) must be used exactly once. This is the definition of finding an Eulerian Path in a directed graph. 3. Lexical Order: If multiple valid paths exist, we need the lexicographically smallest one. For example, ['JFK', 'ATL'] < ['JFK', 'SFO'].

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Graph

332. Reconstruct Itinerary

Model: qwen3.5:9b
Topics: Depth-first Search,Graph
FAANG asked: 1
Acceptance rate: 38.1%


Problem Breakdown

We need to reconstruct an itinerary from a set of airline tickets. The core constraints define the problem structure:

  1. Start Node: Must begin at “JFK”.
  2. Edge Usage: Every ticket (directed edge) must be used exactly once. This is the definition of finding an Eulerian Path in a directed graph.
  3. Lexical Order: If multiple valid paths exist, we need the lexicographically smallest one. For example, ["JFK", "ATL"] < ["JFK", "SFO"].

Inputs: A list of [from, to] pairs (tickets). Outputs: An ordered list of airport codes representing the path. Implicit Constraints: The graph is directed. We assume a valid Eulerian path exists starting from JFK. Since we must use all edges and start at JFK, this implies specific degree constraints on nodes (in-degree = out-degree for intermediate nodes), but since validity is guaranteed by problem statement, we focus on traversal logic rather than validation checks.

Intuition

A brute-force approach would try every permutation of tickets to find a valid path starting from “JFK”. This has factorial time complexity O(N!)O(N!) and will fail given the constraint tickets.length <= 300. We need something polynomial.

Recognizing this as an Eulerian Path problem, we can use Depth-First Search (DFS). However, standard DFS doesn’t guarantee lexical order or handle edge removal efficiently without backtracking overhead. The key insight is Hierholzer’s Algorithm logic adapted for recursion: traverse edges until stuck, then backtrack and add nodes to the result list in post-order.

To satisfy the “smallest lexical order” requirement while maintaining O(1)O(1) efficiency when removing used tickets from our adjacency lists, we must sort neighbors carefully. If we store destinations sorted descending, pop() removes the lexicographically smallest neighbor (which sits at index -1). This avoids shifting array elements (O(N)O(N)) and ensures we greedily try smaller airports first during traversal.

Approach

  1. Build Adjacency List: Use a hash map (defaultdict(list)). For each ticket [u, v], append v to the list of neighbors for u.
  2. Sort Neighbors: Sort every neighbor list in descending order (e.g., ['SFO', 'ATL']). This allows us to access and remove the lexicographically smallest destination efficiently using a stack-like pop operation from the end of the list (O(1)O(1)).
  3. DFS Traversal: Start DFS at “JFK”. For each node, while it has neighbors:
    • Pop the neighbor (smallest lexical) from its adjacency list.
    • Recursively call DFS on that neighbor.
  4. Post-Order Construction: After visiting all reachable edges from a current node (recursion returns), append the current airport to our result list (res). This naturally builds the path in reverse order of visitation because we only add nodes once their outgoing paths are fully explored.
  5. Finalize: Reverse res at the end so it starts with “JFK” and ends with the final destination.

Complexity Analysis

  • Time Complexity: O(Elog⁡E)O(E \log E), where EE is the number of tickets (edges). We sort each adjacency list once (∑di⋅log⁡(di)≤Elog⁡E\sum d_i \cdot \log(d_i) \le E \log E), and DFS visits every edge exactly once. The pop operation is amortized O(1)O(1).
  • Space Complexity: O(V+E)O(V + E) to store the graph (adjacency map). Recursion stack depth can be up to EE, so space for call stack is also proportional to edges in worst case, but bounded by total nodes/edges.

Solution

from collections import defaultdict

def findItinerary(tickets):
    # Build adjacency list with destinations sorted descending 
    # so we can pop the lexicographically smallest neighbor efficiently (O(1))
    graph = defaultdict(list)
    
    for src, dst in tickets:
        graph[src].append(dst)
        
    # Sort each destination list in reverse order.
    # This ensures that when we use stack.pop(), 
    # we retrieve the lexicographically smallest neighbor first.
    for destinations in graph.values():
        destinations.sort(reverse=True)

    itinerary = []
    
    def dfs(airport):
        while airport in graph and graph[airport]:
            next_airport = graph[airport].pop()
            dfs(next_airport)
        
        # Post-order traversal: add node after all its neighbors are visited.
        # This builds the path backwards (end to start).
        itinerary.append(airport)

    dfs("JFK")
    
    return itinerary[::-1]  # Reverse list to get correct order from JFK onwards

Edge Cases Handled

  • Multiple edges between same airports: The adjacency lists store duplicates. Sorting and popping handles multiple flights correctly (e.g., two tickets ["A", "B"] will appear twice in the neighbor list).
  • Cycles: Hierholzer’s logic naturally traverses cycles by backtracking when a node has no remaining outgoing edges, ensuring all edges are used before returning to start.
  • Lexical Order Requirement: Sorting neighbors descending and using pop() ensures we always attempt the lexicographically smallest valid neighbor first during traversal without expensive list shifting.