This problem asks for a full itinerary reconstruction using each ticket exactly once, starting at JFK. A depth-first search approach with a graph structure ensures correct traversal while maintaining lexical order among multiple possible paths. The solution essentially forms an Eulerian path through the directed flight graph, making it crucial to track edges and backtrack carefully when necessary.
Problem Statement
Given a list of airline tickets represented as pairs [from, to], reconstruct the complete itinerary starting from 'JFK'. Each ticket must be used exactly once, and the itinerary should prioritize the smallest lexical order when multiple valid routes exist.
Implement a function that returns the reconstructed itinerary as an array of airport codes, ensuring all tickets are consumed and the traversal follows the depth-first search pattern to form a valid Eulerian path.
Examples
Example 1
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Example details omitted.
Example 2
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- fromi.length == 3
- toi.length == 3
- fromi and toi consist of uppercase English letters.
- fromi != toi
Solution Approach
Graph Construction
Build a directed graph where each node is an airport and edges are flights. Sort outgoing edges in lexical order to guarantee the smallest itinerary when traversing.
Depth-First Search Traversal
Perform DFS starting from 'JFK', recursively visiting the next lexical airport. Remove edges as they are used to avoid revisiting, effectively simulating ticket consumption.
Backtracking and Itinerary Formation
When reaching a node with no remaining outgoing edges, prepend it to the itinerary. Continue backtracking to assemble the full route in reverse order, ensuring all tickets are included exactly once.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(E log E) due to sorting adjacency lists, and space complexity is O(V + E) for the graph and recursive call stack, where V is airports and E is tickets.
What Interviewers Usually Probe
- Candidate identifies graph representation with adjacency lists.
- Candidate sorts destinations to handle lexical order correctly.
- Candidate uses DFS and recognizes Eulerian path formation with backtracking.
Common Pitfalls or Variants
Common pitfalls
- Failing to sort adjacency lists leading to incorrect lexical order.
- Not removing edges after visiting, causing repeated use of the same ticket.
- Appending instead of prepending during backtracking, yielding reversed itinerary.
Follow-up variants
- Allowing multiple starting airports instead of fixed 'JFK'.
- Returning all possible valid itineraries instead of just the smallest lexical order.
- Using BFS instead of DFS for traversal with priority queue for lexical order.
How GhostInterview Helps
- Automatically constructs the graph and sorts edges to ensure lexical order.
- Guides through DFS traversal with backtracking to consume all tickets exactly once.
- Detects common pitfalls such as edge reuse and reversed itinerary formation to correct mistakes in real time.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Reconstruct Itinerary?
The primary pattern is depth-first search on a directed graph to form an Eulerian path while respecting lexical order.
Why is sorting destinations important?
Sorting ensures that among multiple possible flights, the itinerary with the smallest lexical order is chosen consistently.
Can I use BFS instead of DFS for this problem?
DFS is preferred because it naturally handles backtracking and constructing the Eulerian path correctly.
How do I handle tickets with the same departure?
Maintain a sorted list of destinations for each departure and remove edges as tickets are used to avoid duplicates.
What should I do if the itinerary appears reversed?
Prepend nodes during backtracking instead of appending to build the correct order from start to end.
Need direct help with Reconstruct Itinerary instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Reconstruct Itinerary from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The Cracking the Safe problem involves finding the shortest password sequence to unlock a safe using graph traversal and Eulerian circuits.
Open problem page#329 Longest Increasing Path in a MatrixFind the length of the longest increasing path in a matrix with given movement constraints using graph techniques.
Open problem page#310 Minimum Height TreesIdentify all roots of a tree that produce minimum height using graph indegree analysis and topological trimming.
Open problem page