Find itinerary from the given list of departure and arrival airports

Given a list of departure and arrival airports, find the itinerary in order. It may be assumed that departure is scheduled from every airport except the final destination, and each airport is visited only once, i.e., there are no cycles in the route.

For example,

Input:

HKG —> DXB
FRA —> HKG
DEL —> FRA

Output: DEL —> FRA —> HKG —> DXB

Input:

LAX —> DXB
DFW —> JFK
LHR —> DFW
JFK —> LAX

Output: LHR —> DFW —> JFK —> LAX —> DXB

Practice this problem

We can easily solve this problem in linear time using hashing. The idea is to find the source airport and print the itinerary starting from the source airport. To find the source airport, construct a set of destination airports from a given list of tickets. A source airport would be one that is not present in the list of destination airports. Once the source airport is found, traverse the list of tickets to the print itinerary in order using recursion.

Following is the C++, Java, and Python program that demonstrates this:

C++

#include <iostream>

#include <unordered_map>

#include <unordered_set>

#include <algorithm>

using namespace std;

// Utility function to transform an `unordered_map<K, V>` into an `unordered_set<V>`

template <typename K, typename V>

unordered_set<V> transform(unordered_map<K, V> &map)

{

unordered_set<V> set;

transform(map.cbegin(), map.cend(), inserter(set, set.begin()),

[](const pair<K, V> &key_value) {

return key_value.second;

});

return set;

}

// Function to print the itinerary starting from a given source `src`

void printItinerary(unordered_map<string, string> &tickets, string src)

{

string dest = tickets[src];

if (dest == "") {

return;

}

cout << src << " —> " << dest << endl;

printItinerary(tickets, dest);

}

// Function to find the itinerary from the given list of departure

// and arrival airports

void findItinerary(string input[][2], int n)

{

// construct a map from the given list of tickets (departure —> arrival)

unordered_map<string, string> tickets;

for (size_t i = 0; i < n; i++) {

tickets.insert(make_pair(input[i][0], input[i][1]));

}

// construct a set of destination airports

unordered_set<string> destinations = transform(tickets);

// consider each departure airport to find the source airport

for (auto const &pair: tickets)

{

// source airport will not be present in the list of destination airports

if (destinations.find(pair.first) == destinations.end())

{

// when the source airport is found, print the itinerary

printItinerary(tickets, pair.first);

return;

}

int main()

{

// input: list of tickets

string tickets[][2] =

{

{ "LAX", "DXB" },

{ "DFW", "JFK" },

{ "LHR", "DFW" },

{ "JFK", "LAX" }

};

int n = 4;

findItinerary(tickets, n);

return 0;

}

Download Run Code

Output:

LHR —> DFW
DFW —> JFK
JFK —> LAX
LAX —> DXB

Java

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

import java.util.stream.Collectors;

import java.util.stream.Stream;

class Main

{

// Function to print the itinerary starting from a given source `src`

private static void printItinerary(Map<String, String> map, String src)

{

String dest = map.get(src);

if (dest == null) {

return;

}

System.out.println(src + " —> " + dest);

printItinerary(map, dest);

}

// Function to find the itinerary from the given list of departure

// and arrival airports

private static void findItinerary(String[][] input)

{

// construct a map from the given list of tickets (departure —> arrival)

Map<String, String> tickets = Stream.of(input)

.collect(Collectors.toMap(p -> p[0], p -> p[1]));

// construct a set of destination airports

Set<String> destinations = new HashSet<>(tickets.values());

// consider each departure airport to find the source airport

for (String airport: tickets.keySet())

{

// source airport will not be present in the list of destination airports

if (!destinations.contains(airport))

{

// when the source airport is found, print the itinerary

printItinerary(tickets, airport);

return;

}

public static void main(String[] args)

{

// input: list of tickets

String[][] input = new String[][]{

{"LAX", "DXB"},

{"DFW", "JFK"},

{"LHR", "DFW"},

{"JFK", "LAX"}

};

findItinerary(input);

}

Download Run Code

Output:

LHR —> DFW
DFW —> JFK
JFK —> LAX
LAX —> DXB

Python

# Function to print the itinerary starting from a given source `src`

def print_itinerary(dictionary, src):

dest = dictionary.get(src)

if not dest:

return

print(src + ' —> ' + dest)

print_itinerary(dictionary, dest)

# Function to find the itinerary from the given list of departure and arrival airports

def findItinerary(tickets):

# construct a set of destination airports

destinations = {*tickets.values()}

# consider each departure airport to find the source airport

for k, v in tickets.items():

# source airport will not be present in the list of destination airports

if k not in destinations:

# when the source airport is found, print the itinerary

print_itinerary(tickets, k)

return

if __name__ == '__main__':

# input: list of tickets

tickets = {

'LAX': 'DXB',

'DFW': 'JFK',

'LHR': 'DFW',

'JFK': 'LAX'

}

findItinerary(tickets)

Download Run Code

Output:

LHR —> DFW
DFW —> JFK
JFK —> LAX
LAX —> DXB

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of tickets.

Another standard solution is to build a directed graph of departure to arrival airports and perform topological sorting upon it. The time complexity of this solution remains O(n).

Find itinerary from the given list of departure and arrival airports

C++

Java

Python

Share this: