Reconstruct Itinerary

LeetCode Problem #332 (Medium)

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.

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.

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:

Surrounded Regions

Priority Queue

Refer to the Prerequisite Knowledge section in Cheapest Flights Within K Stops:

Cheapest Flights Within K Stops

Min-Heap

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

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/

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.

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.

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.

Lexical 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

Global Variables

// 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;

Find Itinerary Function

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;
}

DFS Helper Function

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);
}