332. Reconstruct Itinerary

HardDepth-First SearchGraphEulerian Circuit

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.

Flowchart Walkthrough

Let's analyze the approach to solve Leetcode 332. Reconstruct Itinerary using the algorithm flowchart available at the Flowchart. We'll evaluate each decision step to deduce the appropriate algorithm:

Is it a graph?

Yes: The problem involves constructing an itinerary from a list of tickets where each ticket represents a direct flight between two points. This can be modeled as a directed graph where nodes are airports and edges are flights between airports.

Is it a tree?

No: The graph is not necessarily a tree because it can have cycles (as there might be multiple flights between the same two airports), and the same node can be visited multiple times in the itinerary.

Is the problem related to directed acyclic graphs (DAGs)?

No: While the graph is directed, it's not acyclic as there can be multiple paths (cycles) due to the possibility of flying back and forth between the same airports.

Is the problem related to shortest paths?

No: The objective is not to find the shortest path; instead, it is to find an Eulerian path (or circuit) through the flight network, visiting each edge exactly once in a specific lexicographical order.

Does the problem involve connectivity?

Yes: We need to determine an Eulerian path that visits all the tickets (edges) from a given starting airport.

Is the graph weighted?

No: There are no weights on the edges concerning cost or distance, just the requirement to use every flight rule (edge) exactly once.

Conclusion: Following the flowchart, since the problem involves finding a path in a directed graph that is not acyclic, not weighted, and involves connectivity issues regarding visiting all edges in a certain order, we proceed to use DFS (Depth-First Search pattern) to traverse and backtrace through the graph to find the required itinerary. The DFS approach is particularly suitable for exploring each node and its edges fully before backtracking, which aligns well with the problem’s need to navigate complex flight paths and backtrack if a dead end is encountered.

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.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the following set of tickets representing flights:

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

We start by representing these tickets as a directed graph:

JFK -> KUL
JFK -> NRT
NRT -> JFK

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

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

Our graph now looks like this, with destinations sorted:

JFK -> ["NRT", "KUL"]
NRT -> ["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:

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

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

["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

Time and Space Complexity

Time Complexity

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

Sorting the tickets list, which has a complexity of O(T log T), where T is the number of tickets.
Building the graph takes O(T) time, as each ticket (src, dst pair) is considered exactly once when adding to the graph.
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:

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).
The itinerary list that, in the worst-case, holds O(T) entries, as each ticket will be converted into a step in the itinerary.
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.

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

Which of these pictures shows the visit order of a depth-first search?

I don't know