332. Reconstruct Itinerary
Reconstruct Itinerary (LeetCode 332) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Simulation / Backtracking Helper subpattern.
How to solve Reconstruct Itinerary
Reconstruct Itinerary is a Stack for Simulation and Backtracking problem, part of Stack Patterns. Use stack for simulation problems like simplify path, decode string, and asteroid collision.
Work towards the solution in these steps:
- Model airports as vertices and tickets as directed edges in a graph.
- Store every outgoing ticket separately, including duplicate destinations, and keep destinations ordered lexicographically.
- A purely greedy walk can reach an airport too early and leave unused tickets impossible to complete; use depth-first traversal while consuming edges.
The reference solution runs in O(T log T) time and O(T) space.
The Reconstruct Itinerary solution and editorial walks through the full approach with reference code.
Problem statement
Each item in tickets describes one directed flight: its first airport is the departure point and its second airport is the destination. An itinerary is a sequence of airports in which every adjacent pair corresponds to a ticket.
Return an itinerary that starts at "JFK" and uses every ticket exactly once. Tickets are individual resources, so duplicate flights must still be used separately.
The input guarantees that at least one complete itinerary exists. If multiple complete itineraries are possible, return the one whose full airport sequence is lexicographically smallest when compared from left to right.
Example 1:
Input: tickets = [["JFK","BOS"],["BOS","DEN"],["DEN","JFK"],["JFK","LIM"],["LIM","BOS"]] Output: ["JFK","BOS","DEN","JFK","LIM","BOS"] Explanation: Starting at JFK, the BOS ticket must be taken before LIM to obtain the smallest possible second airport. The sequence then follows BOS to DEN, DEN to JFK, JFK to LIM, and LIM to BOS, using all five tickets exactly once.
Example 2:
Input: tickets = [["JFK","AMS"],["JFK","BER"],["AMS","BER"],["BER","JFK"]] Output: ["JFK","AMS","BER","JFK","BER"] Explanation: AMS is lexicographically smaller than BER, so the itinerary begins with JFK to AMS. The remaining tickets then force AMS to BER, BER to JFK, and JFK to BER.
Example 3:
Input: tickets = [["JFK","OSL"],["OSL","JFK"],["JFK","RIX"],["RIX","JFK"],["JFK","OSL"]] Output: ["JFK","OSL","JFK","RIX","JFK","OSL"] Explanation: The first ticket must be JFK to OSL and then OSL returns to JFK. At that point, taking the other JFK-to-OSL ticket would strand the route at OSL, so the valid complete itinerary must take JFK to RIX, return to JFK, and finally use the remaining JFK-to-OSL ticket.
Constraints:
- 1 <= tickets.length <= 300 - tickets[i].length == 2 for every valid index i - Each airport code contains exactly 3 uppercase English letters - The itinerary must start at "JFK" - At least one valid itinerary uses every ticket exactly once
Topics and companies
Topics: Graph, Depth-First Search, Stack, Sorting.
How to practise Reconstruct Itinerary on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(T log T) time and O(T) space.
Open Reconstruct Itinerary in the code editor, or read the Reconstruct Itinerary editorial for a worked solution with its approach and complexity analysis.
Where Reconstruct Itinerary sits in the DSA pattern sheet
Problems related to Reconstruct Itinerary
Other problems that use the same Simulation / Backtracking Helper and Stack Patterns techniques:
- Asteroid Collision — Medium, same subpattern
- Baseball Game — Easy, same subpattern
- Decode String — Medium, same subpattern
- Simplify Path — Medium, same subpattern
- Basic Calculator — Hard, same pattern
- Basic Calculator II — Medium, same pattern
Reconstruct Itinerary FAQ
What is the LeetCode number of Reconstruct Itinerary?
Reconstruct Itinerary is LeetCode problem 332, rated Hard.
What pattern is used to solve Reconstruct Itinerary?
Reconstruct Itinerary is a Stack for Simulation and Backtracking problem. It belongs to the Stack Patterns pattern, in the Simulation / Backtracking Helper subpattern.
What is the time complexity of Reconstruct Itinerary?
The reference solution runs in O(T log T) time and O(T) space.