---
description: 'LeetCode Problem #332 (Medium)'
---

# Reconstruct Itinerary

## Problem Statement

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`.

{% hint style="info" %}
Note:

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

## Testcases

```
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.
```

## Prerequisite Knowledge

### Depth-First-Search

Refer to the _Prerequisite Knowledge_ section in **Surrounded Regions**:

{% content-ref url="../week-3/surrounded-regions" %}
[surrounded-regions](../week-3/surrounded-regions)
{% endcontent-ref %}

### Priority Queue

Refer to the _Prerequisite Knowledge_ section in **Cheapest Flights Within K Stops**:

{% content-ref url="../week-2/cheapest-flights-within-k-stops" %}
[cheapest-flights-within-k-stops](../week-2/cheapest-flights-within-k-stops)
{% endcontent-ref %}

### Min-Heap

A [complete binary tree](https://www.programiz.com/dsa/complete-binary-tree) wherein, the key at the root must always have the least value among all the other key values, is known as a min-heap. Every node must have a value that is less than the value of their child node(s). This allows for the inorder traversal to produce the tree elements in ascending order.&#x20;

In its array representation, the index of the left child is given by `2i + 1` and the index of the right child is given by `2i + 2`, where  `i` is the current element.

![Source: https://www.geeksforgeeks.org/binary-heap/](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-MAvRhmx9n4cwnK4XGvH%2F-MAvSTtyHdQtds-lmIUu%2Fimage.png?alt=media\&token=9f97b567-d34b-4ab5-b59f-6af06d8689e2)

## Problem Explanation

In this problem, we are required to construct a sequential itinerary based on the given list of airline tickets which each contain a `[from, to]` pair of three-letter airport names.&#x20;

The traveller begins their journey at the `"JFK"` airport, so our itinerary must always begin with `"JFK"`. The subsequent destinations are mapped out according to their sequential occurrence.

#### Example 1

Consider the following airline tickets to be the input:

`[["MUC", "LHR"], ["JFK", MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`

The adjacency list for the given input could be represented as:

`"JFK" -> "MUC"`

`"MUC" -> "LHR"`

`"LHR" -> "SFO"`

`"SFO" -> "SJC"`

Therefore, the resultant itinerary would be:

`"JFK" -> "MUC" -> "LHR" -> "SFO" -> "SJC"`

In this example, there are no conflicts in terms of the sequential arrangement, which may arise if one airport is visited twice, thus creating more than one valid itinerary.&#x20;

#### Example 2

In case more than one valid itinerary can be generated, the problem stipulates that we must return the itinerary which has the _smallest lexical order_.&#x20;

[Lexical Order](https://en.wikipedia.org/wiki/Lexicographical_order) is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.

We can understand this by considering the following airline tickets to be the input:

`[["JFK", "SFO"], ["JFK", ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]`

One adjacency list for the given input could be represented as:

`"JFK" -> "SFO"`

`"SFO" -> "ATL"`

`"ATL" -> "JFK"`

`"JFK" -> "ATL"`

`"ATL" -> "SFO"`

Therefore, the resultant itinerary would be:

`"JFK" -> "SFO" -> "ATL" -> "JFK" -> "ATL" -> "SFO"`

Another adjacency list for the given input could be represented as:

`"JFK" -> "ATL"`

`"ATL" -> "JFK"`

`"JFK" -> "SFO"`

`"SFO" -> "ATL"`

`"ATL" -> "SFO"`

Therefore, the resultant itinerary would be:

`"JFK" -> "SFO" -> "ATL" -> "JFK" -> "ATL" -> "SFO"`

We would return the latter because the first point of difference which occurs in both lists, is the choice of destinations from `"JFK"` at the beginning. The two options are `"ATL"` and `"SFO"`. Alphabetically, `"ATL"` occurs before `"SFO"`, so this is the option that we process.

## Algorithm

### Depth-First-Search Approach

In this approach, we use DFS to travel to each destination from a given starting point. This in effect, creates an adjacency matrix of`[from, to]` values from the given information. To ensure that the airport names are arranged in the correct lexicographical order, we use a min-heap structure.

1. Declare a global map variable which contains a string and priority queue as the key-value pair to store the information about the airports.
2. Declare a global string vector variable to store the resultant itinerary.

#### Find Itinerary Function

1. Using a min-heap, store the names of the airports in lexicographical order.
2. Begin the DFS process from "JFK" since that is the starting point.

#### DFS Helper Function

1. Pop the airports from the priority queue one-by-one.
2. When each new airport is popped, perform DFS.
3. When the priority queue is empty, add the airport names to the resultant vector and return it.

## Code

{% code title="Global Variables" %}
```cpp
// Min-heap to store airports in lexicographical order
map<string, priority_queue<string, vector<string>, greater<string>>> airports;
// String vector to store the final itinerary
vector<string> itinerary;
```
{% endcode %}

{% code title="Find Itinerary Function" %}
```cpp
vector<string> findItinerary(vector<vector<string>>& tickets) {
    // Build the adjacency list
    for(auto ticket : tickets) {
        airports[ticket[0]].push(ticket[1]);
    }
    // Begin the DFS from "JFK"
    DFS("JFK");
    return itinerary;
}
```
{% endcode %}

{% code title="DFS Helper Function" %}
```cpp
void DFS(string source) {
    // Push the airports into the priority queue in lexicographical order
    while(!airports[source].empty()) {
        string top = airports[source].top();
        airports[source].pop();
        // Peform DFS from each new airport
        DFS(top);
    }
    // At this point, the priority queue is empty
    // Add all of the airports to the resultant vector
    itinerary.insert(itinerary.begin(), source);
}
```
{% endcode %}
