332. Reconstruct Itinerary LeetCode Solution
In this guide, you will get 332. Reconstruct Itinerary LeetCode Solution with the best time and space complexity. The solution to Reconstruct Itinerary problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Reconstruct Itinerary solution in C++
- Reconstruct Itinerary solution in Java
- Reconstruct Itinerary solution in Python
- Additional Resources

Problem Statement of Reconstruct Itinerary
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.
For example, the itinerary [“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 <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi
Complexity Analysis
- Time Complexity: O(|E|\log |E|)
- Space Complexity: O(|E|)
332. Reconstruct Itinerary LeetCode Solution in C++
class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
vector<string> ans;
unordered_map<string, multiset<string>> graph;
for (const vector<string>& ticket : tickets)
graph[ticket[0]].insert(ticket[1]);
dfs(graph, "JFK", ans);
ranges::reverse(ans);
return ans;
}
private:
void dfs(unordered_map<string, multiset<string>>& graph, const string& u,
vector<string>& ans) {
while (graph.contains(u) && !graph[u].empty()) {
const string v = *graph[u].begin();
graph[u].erase(graph[u].begin());
dfs(graph, v, ans);
}
ans.push_back(u);
}
};
/* code provided by PROGIEZ */
332. Reconstruct Itinerary LeetCode Solution in Java
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
LinkedList<String> ans = new LinkedList<>();
Map<String, Queue<String>> graph = new HashMap<>();
for (final List<String> ticket : tickets) {
graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
graph.get(ticket.get(0)).offer(ticket.get(1));
}
dfs(graph, "JFK", ans);
return ans;
}
private void dfs(Map<String, Queue<String>> graph, final String u, LinkedList<String> ans) {
final Queue<String> arrivals = graph.get(u);
while (arrivals != null && !arrivals.isEmpty())
dfs(graph, arrivals.poll(), ans);
ans.addFirst(u);
}
}
// code provided by PROGIEZ
332. Reconstruct Itinerary LeetCode Solution in Python
class Solution:
def findItinerary(self, tickets: list[list[str]]) -> list[str]:
ans = []
graph = collections.defaultdict(list)
for a, b in reversed(sorted(tickets)):
graph[a].append(b)
def dfs(u: str) -> None:
while u in graph and graph[u]:
dfs(graph[u].pop())
ans.append(u)
dfs('JFK')
return ans[::-1]
# code by PROGIEZ
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.