332. Reconstruct Itinerary

HardDepth-First SearchGraphEulerian Circuit
Leetcode Link

Problem Description

The problem provides you with a list of flight tickets represented as pairs of airports, where each pair [from_i, to_i] indicates a flight departing from from_i and arriving at to_i. Your task is to use these tickets to reconstruct a trip itinerary starting from the airport "JFK". Since the man's journey starts from "JFK", the itinerary must also start with "JFK".

You should find an itinerary that uses all the given tickets exactly once. If there are multiple itineraries that satisfy the ticket usage, you need to choose the itinerary that is lexicographically smallest when the sequence of airports is considered as a single string. For example, an itinerary that begins with [“JFK”, “LGA”] is considered smaller than [“JFK”, “LGB”].

The key points to consider for this problem are:

  • The trip must start from "JFK".
  • You must use each ticket exactly once.
  • If multiple itineraries are possible, return the one that is lexicographically smallest.

Intuition

To solve this problem, we take inspiration from graph theory. We can represent the list of tickets as a directed graph where each airport is a vertex and each ticket is a directed edge from from_i to to_i. The objective is to find an Eulerian path through the graph, which is a path that visits every edge exactly once.

To ensure that we visit the smallest lexicographical path first, we sort the outgoing flights (edges) for each airport (vertex) in descending lexical order. We use a recursive depth-first search (DFS) algorithm, starting from "JFK", to build the itinerary. Whenever we reach an airport with no further outgoing flights, we add that airport to the itinerary. Since we're using a recursive approach, the itinerary is constructed in reverse, beginning with the last airport visited.

During the DFS, if there is a dead end (and because the graph has at least one valid itinerary, this dead end is not the starting airport "JFK"), we backtrack to the previous airport and continue the search. This process ensures that we use all tickets. After the DFS is completed, we reverse the constructed itinerary to get the correct order of travel.

This solution utilizes a greedy approach to always take the smallest lexicographical path first while ensuring all edges are visited, fitting the requirements of an Eulerian path where all tickets are used once.

Learn more about Depth-First Search and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution follows a depth-first search (DFS) methodology using a stack that operates on a recursive call stack. The data structure and pattern used are as follows:

  • Graph Representation: We use a defaultdict of lists to represent the directed graph. Each key in this dictionary is an airport, and its value is a list of airports to which there are outbound flights.

  • Sorting: Before we start the DFS, we sort the tickets in reverse order. This ensures that while we add destinations to the graph, they are stored in reverse lexicographical order. Since Python lists function as stacks and we use .pop() to retrieve the last element, we will get the smallest element first due to this initial reverse sorting.

  • Depth-First Search: We create a recursive function dfs that takes an airport as input and explores all possible itineraries from that airport using DFS. If the current airport has no more destinations to visit ([graph](/problems/graph_intro)[airport] is empty), it means we've hit a dead end or finished one valid path, and we add this airport to the itinerary.

  • Building Itinerary: As we are backtracking (when the recursion unwinds), we append the airports to the itinerary. This constructs the itinerary in reverse, as the last airport in our journey will be the first to be added to the itinerary once all its tickets have been used up.

  • Reversing Itinerary: After the DFS completes, we get an itinerary that is in reverse order. To correct this, we simply reverse the itinerary before returning it to get the itinerary in the order of travel.

In this approach, we leverage the call stack of the recursive function to serve as a temporal data structure to hold our path. We guarantee that the path we're constructing is valid and that we are visiting the flights in the smallest lexicographical order as required.

Here's the relevant code breakdown:

  • [graph](/problems/graph_intro) = defaultdict(list) is used to construct the graph.
  • for src, dst in sorted(tickets, reverse=True): graph[src].append(dst) is used for populating the graph with sorted tickets.
  • itinerary = [] is the list that will eventually contain the itinerary, once reversed.
  • dfs("JFK") initiates the DFS from "JFK".
  • itinerary[::-1] reverses the itinerary to return the final solution.

The elegance of the solution lies in how the graph is constructed and traversed, ensuring all tickets are used exactly once and the lexicographically smallest path is found without the need for post-processing or backtracking beyond what's natural to DFS.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Consider the following set of tickets representing flights:

1[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

We start by representing these tickets as a directed graph:

1JFK -> KUL
2JFK -> NRT
3NRT -> JFK

Firstly, we need to sort the destinations in descending lexicographical order for each airport.

  1. For "JFK", the destinations "KUL" and "NRT" are sorted as ["NRT", "KUL"].
  2. "NRT" only has one destination: "JFK".

Our graph now looks like this, with destinations sorted:

1JFK -> ["NRT", "KUL"]
2NRT -> ["JFK"]

Now, we apply the depth-first search (DFS) approach starting from "JFK".

  • Begin at "JFK". Available destinations are "NRT" and "KUL", we choose "NRT" as it is lexicographically smaller.
  • At "NRT", the only destination is "JFK". We go there.
  • Back at "JFK", the only remaining destination is "KUL". We go there.
  • Now, we are at "KUL" with no further destinations to explore.

As we reach each "end" of a path, we add the airport to the itinerary. Since "KUL" has no further destinations, "KUL" is added to the itinerary first.

The constructed itinerary in reverse is:

1["KUL", "JFK", "NRT", "JFK"]

Finally, we reverse the itinerary to get the correct travel order:

1["JFK", "NRT", "JFK", "KUL"]

This itinerary has utilized all tickets exactly once and is lexicographically the smallest, fulfilling all the problem requirements.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
5        # Create a default dictionary to represent the graph where each
6        # key is a departure airport and values are lists of arrival airports
7        graph = defaultdict(list)
8
9        # Sort tickets in reverse order, since we will later pop destinations from the end of the list
10        # which is more efficient than pop(0), and we need the smallest lexical order for equal paths.
11        for departure, arrival in sorted(tickets, reverse=True):
12            graph[departure].append(arrival)
13
14        # Initialize a list to keep track of the itinerary
15        itinerary = []
16
17        # Recursive Depth First Search function
18        def dfs(airport):
19            # While there are destinations to visit from current airport
20            while graph[airport]:
21                # Visit the destination by doing DFS on the last airport in the list
22                # (since it's reversed sorted, smallest lexical goes last)
23                dfs(graph[airport].pop())
24            # Append the airport to itinerary after visiting all destinations
25            itinerary.append(airport)
26
27        # Begin DFS from 'JFK' which is the starting airport
28        dfs("JFK")
29
30        # The itinerary is in reverse order due to the nature of DFS, so reverse it before returning
31        return itinerary[::-1]
32
33# Note: List needs to be imported from typing to use List type annotations.
34from typing import List
35
1import java.util.*;
2
3public class Solution {
4
5    // Performs Depth-First Search recursively on the graph.
6    private void dfs(Map<String, PriorityQueue<String>> graph, LinkedList<String> itinerary, String currentNode) {
7        // Retrieve the neighbors (destinations) for the current node
8        PriorityQueue<String> neighbors = graph.get(currentNode);
9      
10        // Process all neighbors
11        while (neighbors != null && !neighbors.isEmpty()) {
12            // Remove the top neighbor (next destination) from the queue and perform dfs
13            String nextNode = neighbors.poll();
14            dfs(graph, itinerary, nextNode);
15        }
16      
17        // All flights from the current node have been used; add to the itinerary
18        itinerary.addFirst(currentNode);
19    }
20
21    public List<String> findItinerary(List<List<String>> tickets) {
22        // Create a graph from the list of tickets. Each node maps to a priority queue of destinations
23        Map<String, PriorityQueue<String>> graph = new HashMap<>();
24        for (List<String> ticket : tickets) {
25            String src = ticket.get(0);  // Source airport
26            String dest = ticket.get(1); // Destination airport
27          
28            // Initialize the priority queue if it does not already exist
29            graph.computeIfAbsent(src, k -> new PriorityQueue<>()).add(dest);
30        }
31      
32        // This linked list will store the itinerary in reverse order
33        LinkedList<String> itinerary = new LinkedList<>();
34      
35        // Start DFS from the "JFK" node
36        dfs(graph, itinerary, "JFK");
37      
38        // The LinkedList itinerary already contains the nodes in reverse due to the use of addFirst().
39        // Therefore, there's no need to reverse the itinerary at the end.
40        return itinerary;
41    }
42}
43
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <queue>
5using namespace std;
6
7class Solution {
8public:
9    // Function to find the itinerary from a list of tickets
10    vector<string> findItinerary(vector<vector<string>>& tickets) {
11        // Graph to hold nodes and edges where the edges are sorted in a min-heap (priority queue)
12        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
13        vector<string> result; // This will hold the final itinerary
14
15        // Build the graph
16        for (const auto& ticket : tickets) {
17            graph[ticket[0]].push(ticket[1]);
18        }
19
20        // DFS to build the itinerary
21        findItineraryDFS(graph, result, "JFK");
22
23        // The DFS result is in reverse order, reverse it to get the correct itinerary
24        reverse(result.begin(), result.end());
25
26        return result;
27    }
28
29    // Helper DFS function to add the itinerary in reverse order
30    void findItineraryDFS(unordered_map<string, priority_queue<string, vector<string>, greater<string>>>& graph, vector<string>& result, string currentNode) {
31        // Iterate as long as there are destinations from the current node
32        while (!graph[currentNode].empty()) {
33            // Get the next destination in lexical order
34            string nextDestination = graph[currentNode].top();
35            graph[currentNode].pop(); // Remove the edge to the next destination
36            findItineraryDFS(graph, result, nextDestination); // DFS with the next node
37        }
38        // Add the current node to the result list
39        result.push_back(currentNode);
40    }
41};
42
1import { PriorityQueue } from 'typescript-collections';
2
3// The graph will map nodes to a priority queue of destinations.
4const graph: Record<string, PriorityQueue<string>> = {};
5// An array to hold the final itinerary.
6let itinerary: string[] = [];
7
8// Function to find the itinerary from a list of tickets.
9function findItinerary(tickets: [string, string][]): string[] {
10    // Build the graph with destinations sorted in lexical order.
11    tickets.forEach(([from, to]) => {
12        if (!graph[from]) {
13            graph[from] = new PriorityQueue<string>((a, b) => a < b ? -1 : (a > b ? 1 : 0));
14        }
15        graph[from].enqueue(to);
16    });
17
18    // Perform the depth-first search starting from "JFK".
19    dfs("JFK");
20
21    // The DFS result is in reverse order, so it's reversed to get the correct itinerary.
22    itinerary.reverse();
23
24    return itinerary;
25}
26
27// Helper DFS function to recursively build the itinerary.
28function dfs(node: string): void {
29    // Continue until all destinations from the current node have been visited.
30    let destinations = graph[node];
31    while (destinations && !destinations.isEmpty()) {
32        // Visit the next destination in lexical order.
33        const nextDestination = destinations.dequeue();
34        dfs(nextDestination);
35    }
36    // Add the current node to the result list.
37    itinerary.push(node);
38}
39
40// Please note, the PriorityQueue class used in this sample is hypothetical and assumed to be from 
41// an npm package like 'typescript-collections'. The actual implementation may differ.
42
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

Time Complexity

The time complexity of the algorithm can be broken down into the following parts:

  1. Sorting the tickets list, which has a complexity of O(T log T), where T is the number of tickets.
  2. Building the graph takes O(T) time, as each ticket (src, dst pair) is considered exactly once when adding to the graph.
  3. The depth-first search (DFS) uses recursion and, in the worst case, visits each vertex and edge once. Since each ticket represents a directed edge in the graph, the complexity for the DFS part is O(T).

Combining these gives us a total time complexity of T(sorting) + T(building graph) + T(DFS) -> O(T log T) + O(T) + O(T), which simplifies to O(T log T) due to the dominance of the sorting complexity.

Space Complexity

The space complexity is determined by:

  1. The space needed for the graph data structure, which can hold at most 2T entries (because each ticket is a directed edge and might introduce up to two vertices).
  2. The itinerary list that, in the worst-case, holds O(T) entries, as each ticket will be converted into a step in the itinerary.
  3. The depth of the call stack for the recursive DFS function, which, in the worst case, could be O(T) if the graph forms a straight line.

The graph size dominates and offers a space complexity of O(T). The call stack and the final itinerary list also contribute O(T) each. Thus, the total space complexity is O(T) + O(T) + O(T), which simplifies to O(T), since all are linear with respect to the number of tickets.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫