332. Reconstruct Itinerary
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 EvaluatorExample 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 ofO(T log T)
, whereT
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 most2T
entries (because each ticket is a directed edge and might introduce up to two vertices). - The
itinerary
list that, in the worst-case, holdsO(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.
Which of the following is a good use case for backtracking?
Recommended Readings
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
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!