Reconstruct Itinerary
Problem
Given a list of airline tickets represented as pairs of departure and arrival airports [from, to], reconstruct the itinerary in order such that all tickets are used exactly once and the itinerary starts from 'JFK'. If multiple valid itineraries exist, return the itinerary that is lexicographically smallest.
- 1 ≤ tickets.length ≤ 300
- tickets[i].length == 2
- from_i.length == 3
- to_i.length == 3
- from_i and to_i consist of uppercase English letters.
Example
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]["JFK", "MUC", "LHR", "SFO", "SJC"]Starting from 'JFK', the algorithm explores destinations in lexicographical order. It first chooses 'MUC' from 'JFK', then 'LHR' from 'MUC', followed by 'SFO' from 'LHR', and finally 'SJC' from 'SFO'. This path uses all tickets exactly once and is lexicographically smallest.
Approach
Straightforward Solution
A brute-force approach tries all permutations of tickets to find a valid itinerary, which is factorial in time and infeasible for large inputs.
Core Observation
The problem requires finding a path that uses all edges (tickets) exactly once in a directed graph, starting from a fixed node 'JFK'. This is a classic Eulerian path problem with the added constraint of lexicographical order.
Path to Optimal
Recognizing the problem as finding an Eulerian path allows the use of Hierholzer's algorithm or backtracking with pruning. Sorting the adjacency lists lexicographically ensures the lexicographically smallest path is found first. Backtracking tries each edge in order, removing it temporarily to avoid reuse, and restores it if the path does not lead to a solution.
Optimal Approach
Build an adjacency list mapping each source to a lexicographically sorted list of destinations. Use backtracking starting from 'JFK', at each step choosing the next lexicographically smallest destination, removing the edge from the adjacency list, and recursively continuing. If the path uses all tickets, return true to stop further search. Restore edges on backtrack to explore alternatives if needed.
Time
O(E!) in the worst case
Backtracking explores permutations of edges, but sorting and pruning reduce the search space significantly. The worst case is factorial in the number of tickets due to permutations, but pruning stops early once a valid path is found.
Space
O(V + E)
The adjacency list stores all edges, and recursion stack can go as deep as the number of tickets (edges). Auxiliary space is proportional to vertices and edges.
Pattern Spotlight
Backtracking (State Restoration with Lexicographical Ordering)
When searching for a path that must use all edges exactly once with lexicographical constraints, use backtracking that tries edges in sorted order, removing edges as they are used and restoring them upon backtracking to maintain correct state and enable pruning.
Solution
| 1 | import collections
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def findItinerary(self, tickets: list[list[str]]) -> list[str]:
|
| 5 | adj = {src: [] for src, dst in tickets}
|
| 6 | tickets.sort()
|
| 7 | for src, dst in tickets:
|
| 8 | adj[src].append(dst)
|
| 9 |
|
| 10 | res = ["JFK"]
|
| 11 | def dfs(src):
|
| 12 | if len(res) == len(tickets) + 1:
|
| 13 | return True
|
| 14 | if src not in adj:
|
| 15 | return False
|
| 16 |
|
| 17 | temp = list(adj[src])
|
| 18 | for i, v in enumerate(temp):
|
| 19 | adj[src].pop(i)
|
| 20 | res.append(v)
|
| 21 | if dfs(v):
|
| 22 | return True
|
| 23 | adj[src].insert(i, v)
|
| 24 | res.pop()
|
| 25 | return False
|
| 26 |
|
| 27 | dfs("JFK")
|
| 28 | return res |
Step-by-Step Solution
Build Lexicographically Sorted Adjacency List
| 5 | adj = {src: [] for src, dst in tickets}
|
| 6 | tickets.sort()
|
| 7 | for src, dst in tickets:
|
| 8 | adj[src].append(dst)
|
Objective
To construct a graph representation where each source airport maps to a sorted list of destination airports, enabling lexicographical traversal.
Key Insight
Sorting the tickets before building the adjacency list ensures that destinations are appended in lexicographical order. This ordering is critical because the backtracking algorithm relies on exploring edges in sorted order to find the lexicographically smallest itinerary first.
Interview Quick-Check
Core Logic
Sorting tickets upfront guarantees adjacency lists are lexicographically ordered, enabling efficient backtracking without additional sorting.
Common Pitfalls & Bugs
Failing to sort the tickets or adjacency lists can lead to incorrect or non-lexicographically minimal itineraries.
Initialize Result and Define Backtracking DFS
| 10 | res = ["JFK"]
|
| 11 | def dfs(src):
|
| 12 | if len(res) == len(tickets) + 1:
|
| 13 | return True
|
| 14 | if src not in adj:
|
| 15 | return False
|
Objective
To prepare the result list starting from 'JFK' and define a recursive DFS function that attempts to build a valid itinerary using all tickets.
Key Insight
Starting the result with 'JFK' sets the fixed starting point. The DFS function attempts to extend the itinerary by exploring all possible next destinations from the current airport. It uses the length of the result to determine when all tickets have been used, enabling early termination.
Interview Quick-Check
Core Logic
The DFS uses the length of the current itinerary to detect completion, ensuring all tickets are used exactly once.
State & Boundaries
The base case returns true when the itinerary length equals the number of tickets plus one, indicating a complete path.
Explore Next Destinations with Backtracking and State Restoration
| 17 | temp = list(adj[src])
|
| 18 | for i, v in enumerate(temp):
|
| 19 | adj[src].pop(i)
|
| 20 | res.append(v)
|
| 21 | if dfs(v):
|
| 22 | return True
|
| 23 | adj[src].insert(i, v)
|
| 24 | res.pop()
|
| 25 | return False
|
Objective
To recursively try each possible next destination from the current airport, removing the edge to prevent reuse and restoring it if the path does not lead to a solution.
Key Insight
Copying the adjacency list for iteration avoids issues with modifying the list during traversal. Removing the edge before recursion prevents reuse of the same ticket. If recursion fails, restoring the edge and popping the last airport from the result restores the state for alternative paths. This careful state management is essential for correctness and efficiency.
Interview Quick-Check
Core Logic
Backtracking tries each edge in lexicographical order, removing it to prevent reuse and restoring it on failure to explore alternatives.
Common Pitfalls & Bugs
Modifying the adjacency list while iterating without copying can cause skipped edges or runtime errors.
State & Boundaries
Returning true immediately upon finding a valid complete itinerary prunes the search space, improving efficiency.
Invoke DFS from 'JFK' and Return Final Itinerary
| 27 | dfs("JFK")
|
| 28 | return res |
Objective
To start the backtracking search from 'JFK' and return the constructed itinerary after successful completion.
Key Insight
The initial call to DFS triggers the recursive exploration of all possible itineraries. Since the algorithm returns as soon as a valid itinerary is found, the final result is guaranteed to be lexicographically smallest due to the sorted adjacency lists.
Interview Quick-Check
Core Logic
Starting DFS from 'JFK' ensures the itinerary begins at the required airport.
Complexity
The early return upon success prevents unnecessary exploration of all permutations, improving practical runtime.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
adj[src].pop(i)Remove the destination from the original adjacency list to mark the ticket as used.
Removing the edge prevents reuse of the same ticket, ensuring each ticket is used exactly once in the itinerary.
adj[src].insert(i, v)Restore the removed destination to the adjacency list upon backtracking.
Restoring the edge allows alternative paths to be explored, maintaining correct state for backtracking.
res.pop()Remove the last added destination from the itinerary to backtrack.
Removing the last airport restores the path state, enabling exploration of other possible itineraries.
tickets.sort()Sort the tickets lexicographically by source and destination.
Sorting ensures that when destinations are appended to adjacency lists, they are in lexicographical order, which is crucial for finding the lexicographically smallest itinerary.
if len(res) == len(tickets) + 1:Check if the itinerary uses all tickets plus one airport.
This base case detects when a complete valid itinerary has been constructed, enabling early termination of recursion.
temp = list(adj[src])Create a copy of the current airport's adjacency list for safe iteration.
Copying prevents issues from modifying the adjacency list during iteration, preserving correct traversal order and state.
return TrueReturn true immediately if a complete itinerary is found.
Early return prunes the search space, avoiding unnecessary exploration once a valid path is discovered.
res = ["JFK"]Initialize the result itinerary starting with 'JFK'.
Starting the itinerary with 'JFK' sets the fixed starting point as required by the problem, forming the base of the path to be extended.
return TrueReturn true to signal a complete itinerary has been found.
Returning true propagates success up the recursion stack, preventing further unnecessary exploration.
res.append(v)Append the chosen destination to the current itinerary.
Adding the destination extends the current path, representing the choice of this ticket in the itinerary.
if dfs(v):Recursively attempt to build the itinerary from the chosen destination.
Recursion explores deeper paths, attempting to use all remaining tickets from the new airport.
return FalseReturn false if no valid itinerary is found from current airport.
Returning false signals the need to backtrack further and try different edges.
adj = {src: [] for src, dst in tickets}Initialize adjacency list with empty lists for each source airport.
Creating a dictionary with keys as source airports and empty lists prepares the graph structure to store destinations, enabling efficient edge insertion.
adj[src].append(dst)Append the destination airport to the source's adjacency list.
Appending destinations in sorted order maintains the lexicographical order required for the backtracking search.
def dfs(src):Define the recursive DFS function to build the itinerary.
Encapsulating the backtracking logic in a helper function allows recursive exploration of all possible itineraries from a given airport.
if src not in adj:Check if the current airport has no outgoing edges.
If no destinations remain from the current airport, the path cannot be extended, so this branch fails.
return FalseReturn false to indicate no valid path from current airport.
Returning false triggers backtracking to explore alternative paths.
for i, v in enumerate(temp):Enumerate over the copied list of next destinations.
Enumerating with indices allows precise removal and restoration of edges during backtracking.
dfs("JFK")Start the backtracking search from 'JFK'.
Initiating DFS from 'JFK' ensures the itinerary begins at the required starting airport.
return resReturn the constructed itinerary after successful backtracking.
Returning the result provides the final valid itinerary that uses all tickets exactly once and is lexicographically smallest.
for src, dst in tickets:Iterate over each ticket to build the adjacency list.
This loop populates the adjacency list by mapping each source airport to its destinations, establishing the graph representation of the tickets.
Test Your Understanding
Why must edges be removed from the adjacency list when used and restored upon backtracking?
Removing edges prevents reuse of the same ticket, ensuring each ticket is used exactly once. Restoring edges upon backtracking allows exploring alternative paths, maintaining correctness of the search state.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Reconstruct Itinerary from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reconstruct Itinerary drill