Leetcode 332. Reconstruct Itinerary
Given a list of directed flight tickets, reconstruct an itinerary starting at "JFK" that uses every ticket exactly once and, among all valid itineraries, returns the lexicographically smallest sequence. The core challenge is finding an Eulerian path in a directed graph while prioritizing lexicographically smaller outgoing destinations.
Asked at:
DESCRIPTION
Given a list of directed flight tickets, reconstruct an itinerary starting at "JFK" that uses every ticket exactly once and, among all valid itineraries, returns the lexicographically smallest sequence. The core challenge is finding an Eulerian path in a directed graph while prioritizing lexicographically smaller outgoing destinations.
Input:
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output:
["JFK","MUC","LHR","SFO","SJC"]
Explanation: Starting from JFK, we go to MUC (only option), then LHR (only option), then SFO (only option), then SJC (only option). This uses all tickets exactly once.
Constraints:
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- from_i and to_i consist of uppercase English letters
- from_i != to_i
- All tickets form at least one valid itinerary starting from "JFK"
- You must use all tickets exactly once
Understanding the Problem
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?
Building Intuition
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.
Common Mistakes
Optimal Solution
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 defaultdictdef 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 ordergraph = defaultdict(list)for src, dst in tickets:graph[src].append(dst)# Sort destinations for each airport to ensure lexicographical orderfor src in graph:graph[src].sort(reverse=True)# Result will be built in reverse orderitinerary = []def dfs(airport):# Visit all destinations from current airportwhile 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 JFKdfs("JFK")# Reverse to get correct order (we built it backwards)return itinerary[::-1]
Start reconstructing itinerary from JFK using Hierholzer's algorithm
0 / 29
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(E log E) We have E edges (tickets). Building the adjacency list and sorting destinations takes O(E log E). The DFS visits each edge exactly once, taking O(E). Overall: O(E log E) for sorting dominates.
Space Complexity: O(E) The adjacency list stores all E edges. The recursion stack can go as deep as E in the worst case (a long chain of flights). The result array stores V vertices (airports). Overall: O(E) space.
What We've Learned
- 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.
Related Concepts and Problems to Practice
medium
This problem requires finding a topological ordering of courses, which is conceptually similar to finding an Eulerian path. Both involve traversing all edges in a directed graph exactly once while respecting constraints, and both require careful graph traversal with ordering considerations.
medium
Like reconstructing an itinerary, this problem requires exploring paths through a structure (grid vs graph) and backtracking when paths don't work out. Both problems involve using all available elements exactly once and require systematic exploration with the ability to undo choices.
medium
This problem involves validating graph structure using DFS, which shares the core graph traversal mechanics needed for the itinerary problem. Understanding how to traverse graphs while tracking visited nodes and detecting cycles is fundamental to solving Eulerian path problems.
Test Your Understanding
Why is graph the right data structure for this problem?
graph provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid October, 2025
Senior
Late September, 2025
Staff
Late June, 2025
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.