# Reconstruct Itinerary LeetCode Solution

Here, We see Reconstruct Itinerary LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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.

## Reconstruct Itinerary LeetCode SolutionC++

``````class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
unordered_map<string, vector<string>> graph;
for (auto& ticket : tickets) {
graph[ticket[0]].push_back(ticket[1]);
}
for (auto& [_, destinations] : graph) {
sort(destinations.rbegin(), destinations.rend());
}
vector<string> itinerary;
function<void(const string&)> dfs = [&](const string& airport) {
while (!graph[airport].empty()) {
string next = graph[airport].back();
graph[airport].pop_back();
dfs(next);
}
itinerary.push_back(airport);
};
dfs("JFK");
reverse(itinerary.begin(), itinerary.end());
return itinerary;
}
};``````

## Reconstruct Itinerary LeetCode SolutionJava

``````class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (List<String> ticket : tickets) {
graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
}
dfs("JFK", graph, itinerary);
return itinerary;
}
private void dfs(String airport, Map<String, PriorityQueue<String>> graph, LinkedList<String> itinerary) {
PriorityQueue<String> nextAirports = graph.get(airport);
while (nextAirports != null && !nextAirports.isEmpty()) {
dfs(nextAirports.poll(), graph, itinerary);
}
}
}```Code language: JavaScript (javascript)```

## Reconstruct Itinerary Solution JavaScript

``````var findItinerary = function(tickets) {
const graph = {};
for (const [src, dst] of tickets) {
if (!graph[src]) graph[src] = [];
graph[src].push(dst);
}
for (const key in graph) {
graph[key].sort().reverse();
}
const itinerary = [];
function dfs(airport) {
while (graph[airport] && graph[airport].length > 0) {
dfs(graph[airport].pop());
}
itinerary.push(airport);
}
dfs("JFK");
return itinerary.reverse();
};```Code language: JavaScript (javascript)```

## Reconstruct Itinerary SolutionPython

``````class Solution(object):
def findItinerary(self, tickets):
graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
itinerary = []
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop())
itinerary.append(airport)
dfs("JFK")
return itinerary[::-1]``````
Scroll to Top