# Solution For Reconstruct Itinerary

The Reconstruct Itinerary problem on LeetCode requires you to reconstruct the itinerary based on a list of flight tickets.

The input to the problem is a list of flight tickets represented as a list of lists. Each ticket is represented by a list containing the source airport and the destination airport. The first airport in the list is the starting airport.

The output should be a list containing the itinerary in the correct order.

To solve the problem, you can use a recursive approach. Starting at the starting airport, you can find all the destinations from the current airport and recursively try to find an itinerary from each destination.

To optimize the solution, you can use a dictionary to keep track of all the flights and their destinations. This will allow you to quickly find the destinations for a given airport.

Here is the Python code for the solution:

“`
def findItinerary(tickets: List[List[str]]) -> List[str]:
def visit(airport):
while flights.get(airport):
visit(flights[airport].pop(0))
itinerary.append(airport)

``````flights = {}
for start, end in tickets:
if start not in flights:
flights[start] = []
flights[start].append(end)
for start in flights:
flights[start].sort()

itinerary = []
visit('JFK')
return itinerary[::-1]
``````

“`

The function first creates a dictionary called flights to store all the flights and their destinations. It then sorts the destinations for each airport to ensure that the itinerary is in lexicographic order.

The visit function uses recursion to traverse the flight itinerary. It starts at the current airport and continues to visit the next destination until there are no more destinations left. It then adds the current airport to the itinerary.

Finally, the function calls the visit function starting at the starting airport and returns the itinerary in reverse order to get the correct order.

## Step by Step Implementation For Reconstruct Itinerary

```import java.util.*;

public class Solution {
public List findItinerary(String[][] tickets) {
// create a map of the tickets
Map> map = new HashMap<>();
for (String[] ticket : tickets) {
if (!map.containsKey(ticket[0])) {
map.put(ticket[0], new PriorityQueue<>());
}
}
// create a list to store the itinerary
List itinerary = new ArrayList<>();
// create a stack to keep track of the path
Stack stack = new Stack<>();
// start from JFK
stack.push("JFK");
// while the stack is not empty
while (!stack.isEmpty()) {
// get the top element of the stack
String airport = stack.peek();
// if the map contains the airport
if (map.containsKey(airport)) {
// get the list of destinations from the map
PriorityQueue destinations = map.get(airport);
// if the list of destinations is not empty
if (!destinations.isEmpty()) {
// remove the top destination from the list
String dest = destinations.poll();
// push the destination to the stack
stack.push(dest);
}
// if the list of destinations is empty
else {
// add the airport to the itinerary
// remove the airport from the stack
stack.pop();
}
}
// if the map does not contain the airport
else {
// add the airport to the itinerary
// remove the airport from the stack
stack.pop();
}
}
// return the itinerary
return itinerary;
}
}```
```Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

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"].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
One must use all the tickets once and only once.
Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Example 2:

Input: [["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.

def findItinerary(tickets):
# create a map of all the tickets
# the key is the departure airport
# the value is a list of all the arrival airports
ticket_map = collections.defaultdict(list)
for ticket in tickets:
ticket_map[ticket[0]].append(ticket[1])

# sort the values in the map in lexical order
for key in ticket_map:
ticket_map[key].sort()

# create a list to store the itinerary
# we will be using a stack to keep track of the airports
itinerary = []
stack = ['JFK']

# while the stack is not empty
while stack:
# pop the top airport from the stack
curr = stack.pop()
# add it to the itinerary
itinerary.append(curr)
# if there are any tickets with the current airport as the departure
if curr in ticket_map:
# sort the tickets in lexical order
ticket_map[curr].sort()
# add all the arrival airports to the stack
for airport in ticket_map[curr]:
stack.append(airport)

# return the itinerary in reverse order
return itinerary[::-1]```
```var findItinerary = function(tickets) {
// create a map of all the destinations
let map = {};
for (let i = 0; i < tickets.length; i++) {
let curr = tickets[i];
if (!map[curr[0]]) {
map[curr[0]] = [curr[1]];
} else {
map[curr[0]].push(curr[1]);
}
}

// sort the destinations in alphabetical order
for (let key in map) {
map[key].sort();
}

// create the itinerary
let itinerary = [];
let createItinerary = function(curr) {
while (map[curr] && map[curr].length > 0) {
createItinerary(map[curr].shift());
}
itinerary.unshift(curr);
};

createItinerary('JFK');
return itinerary;
};```
```There are a few key points to this problem:

1) We need to find the Eulerian path in the given graph.
2) The given graph is directed, so we need to find the Hamiltonian path.
3) We need to use the Hierholzer's algorithm to find the Eulerian path.

The code for this solution is as follows:

#include
#include
#include
#include

using namespace std;

class Solution {
public:
vector findItinerary(vector> tickets) {
// Build the graph
unordered_map> graph;
for (auto& ticket : tickets) {
graph[ticket.first].insert(ticket.second);
}

// Find the Eulerian path
vector path;
string curr = "JFK";
dfs(graph, curr, path);
return vector(path.rbegin(), path.rend());
}

void dfs(unordered_map>& graph, string curr, vector& path) {
while (!graph[curr].empty()) {
string next = *graph[curr].begin();
graph[curr].erase(graph[curr].begin());
dfs(graph, next, path);
}
path.push_back(curr);
}
};```
```var findItinerary = function(tickets) {

// create a map of all the destinations and their corresponding ticket
let map = new Map();
for (let i=0; i 0) {
// get the next ticket and remove it from the list
let next = tickets.shift();
dfs(next);
}
// once we reach a destination with no more tickets, we can add it to our itinerary
itinerary.unshift(curr);
};

// start from JFK
dfs('JFK');
return itinerary;
};```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]