You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints:
1 <= tickets.length <= 300tickets[i].length == 2fromi.length == 3toi.length == 3fromi and toi consist of uppercase English letters.fromi != toiThe Reconstruct Itinerary problem can be modeled as a directed graph where each ticket represents an edge from one airport to another. The goal is to use all tickets exactly once while producing the lexicographically smallest valid itinerary. This structure closely resembles finding an Eulerian path in a graph.
A common strategy is to build an adjacency list where each airport maps to its destinations. To ensure lexical order, store destinations in a min-heap or sort them beforehand. Then apply Depth-First Search (DFS) following the idea behind Hierholzer’s algorithm for Eulerian paths. During DFS, repeatedly visit the smallest available destination and remove the edge once used. Airports are added to the itinerary during the backtracking phase.
This approach guarantees that every ticket is used exactly once while maintaining lexical order. The main cost comes from sorting or heap operations when selecting the next destination.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Hierholzer’s Algorithm and Min-Heap | O(E log E) | O(E) |
| DFS with Pre-sorted Adjacency Lists | O(E log E) | O(E) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS naturally supports the backtracking behavior required by Hierholzer’s algorithm. By exploring edges until none remain and adding nodes during backtracking, it constructs a valid Eulerian path that uses all tickets exactly once.
Yes, Reconstruct Itinerary is considered a classic graph and DFS interview problem. It tests understanding of Eulerian paths, graph traversal, and careful handling of lexical ordering, which are common themes in FAANG-style interviews.
An adjacency list combined with a min-heap (priority queue) is commonly used. This structure allows you to always pick the lexicographically smallest destination efficiently while performing DFS traversal.
The optimal approach models the problem as finding an Eulerian path in a directed graph. Using DFS with Hierholzer’s algorithm ensures every ticket (edge) is used exactly once while constructing the path in reverse order. A min-heap or sorted adjacency list helps maintain the lexicographically smallest itinerary.