Reconstruct Itinerary
HardPrompt
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
- For example, the itinerary
["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.
Constraints:
1 <= tickets.length <= 300tickets[i].length == 2fromi.length == 3toi.length == 3fromiandtoiconsist of uppercase English letters.fromi != toi
Approaches
2 approaches with complexity analysis and trade-offs.
This approach employs a standard backtracking algorithm using Depth-First Search (DFS). The idea is to explore all possible valid itineraries starting from "JFK". We model the airports and flights as a directed graph. To ensure the final itinerary is the lexicographically smallest, we always explore flights to destinations in alphabetical order. The first complete itinerary found will be the correct answer. We keep track of used tickets to ensure each is used exactly once. If a path leads to a dead end (i.e., we get stuck before using all tickets), we backtrack and try a different path.
Algorithm
- Build a graph where airports are nodes and tickets are directed edges. An adjacency list, like
Map<String, List<String>>, is a good representation. - For each airport, sort its list of destinations lexicographically. This ensures that when exploring from an airport, we try the lexicographically smallest destination first.
- To handle duplicate tickets, we need a way to track which specific ticket has been used. A
Map<String, boolean[]>can be used, where for eachfromairport, we have a boolean array corresponding to its sorted destination list.visited.get("JFK")[0]would track the first flight from JFK in its sorted list of destinations. - Define a recursive DFS function, say
dfs(from, path). - The base case for the recursion is when the path length equals the number of tickets plus one. At this point, a valid itinerary has been found. Since we explore in lexicographical order, the first one we find is the answer, and we can stop the search.
- In the recursive step, for the current airport, iterate through its destinations. For each unused ticket to a destination, mark it as used and make a recursive call for the destination airport.
- If a recursive call returns
true(solution found), propagate this up the call stack. - If the recursive call leads to a dead end (returns
false), we must backtrack. This involves unmarking the ticket as used so it can be part of another path.
Walkthrough
The implementation begins by constructing a graph from the list of tickets. An adjacency list, represented by a HashMap, maps each departure airport to a list of its destinations. Crucially, each list of destinations is sorted lexicographically to guide the DFS towards the smallest lexical itinerary.
To handle duplicate flights (e.g., two tickets from "JFK" to "SFO"), we can't simply mark a destination as visited. Instead, we need to track the usage of each specific ticket. A Map<String, boolean[]> serves this purpose, where for each departure airport, a boolean array tracks the used status of each of its outgoing flights, corresponding to the sorted destination list.
The core of the solution is a recursive dfs function. It attempts to build the itinerary step by step. Starting from "JFK", it tries to fly to the first available destination in the sorted list. It marks that ticket as used and recursively calls itself for the arrival airport. If this path eventually uses all tickets (i.e., the path length becomes num_tickets + 1), a solution is found. If the recursive call fails to find a complete path, it backtracks by unmarking the ticket and trying the next available destination.
class Solution { private Map<String, List<String>> adj = new HashMap<>(); private Map<String, boolean[]> visited; private int numTickets = 0; private List<String> result = null; public List<String> findItinerary(List<List<String>> tickets) { this.numTickets = tickets.size(); for (List<String> ticket : tickets) { String from = ticket.get(0); String to = ticket.get(1); this.adj.computeIfAbsent(from, k -> new ArrayList<>()).add(to); } this.visited = new HashMap<>(); for (Map.Entry<String, List<String>> entry : this.adj.entrySet()) { Collections.sort(entry.getValue()); this.visited.put(entry.getKey(), new boolean[entry.getValue().size()]); } LinkedList<String> path = new LinkedList<>(); path.add("JFK"); dfs("JFK", path); return this.result; } private boolean dfs(String from, LinkedList<String> path) { if (path.size() == this.numTickets + 1) { this.result = new ArrayList<>(path); return true; } if (!this.adj.containsKey(from)) { return false; } List<String> destinations = this.adj.get(from); boolean[] used = this.visited.get(from); for (int i = 0; i < destinations.size(); i++) { if (!used[i]) { used[i] = true; path.add(destinations.get(i)); if (dfs(destinations.get(i), path)) { return true; } path.removeLast(); used[i] = false; } } return false; }}Complexity
Time
O(d^E) in the worst case, where d is the maximum out-degree of an airport and E is the number of tickets. The algorithm might explore a number of paths that is exponential in the number of tickets, making it too slow for the given constraints.
Space
O(V + E), where V is the number of airports and E is the number of tickets. This space is used to store the graph, the visited map, and the recursion stack.
Trade-offs
Pros
Conceptually straightforward and easy to understand for those familiar with DFS and backtracking.
Cons
Highly inefficient and likely to result in a 'Time Limit Exceeded' error for larger inputs.
The search can go very deep down a wrong path before backtracking, especially if the lexicographically smallest choices lead to a dead end where not all tickets can be used.
This problem is equivalent to finding an Eulerian path in a directed graph, for which Hierholzer's algorithm is a perfect fit. This approach is both elegant and efficient. We perform a single pass DFS-like traversal through the graph. The key idea is to build the itinerary backward. When we get stuck at an airport (i.e., there are no more outgoing flights to take), we add it to the head of our result list. To satisfy the lexicographical requirement, we use a PriorityQueue to store the destinations for each airport, ensuring we always visit the alphabetically smallest destination first.
Algorithm
- Represent the flights as a directed graph. Use a
Map<String, PriorityQueue<String>>for the adjacency list. ThePriorityQueuewill ensure that we can always access and remove the lexicographically smallest destination efficiently. - Populate the graph from the input
tickets. For each ticket[from, to], addtoto thePriorityQueueoffrom. - Initialize an empty
LinkedList<String>to store the final itinerary. - Implement a recursive DFS function, say
dfs(airport). - Inside
dfs(airport), get thePriorityQueueof destinations for the currentairport. While the queue is not empty,poll()the next destination and make a recursive call:dfs(nextDestination). - After the
whileloop finishes (meaning all outgoing flights fromairporthave been visited), add theairportto the front of the itinerary list. - Start the process by calling
dfs("JFK"). - The final
itinerarylist will hold the reconstructed path in the correct order.
Walkthrough
The algorithm starts by building a graph representation of the flights. A HashMap where keys are departure airports and values are PriorityQueues of destination airports is ideal. The PriorityQueue naturally maintains destinations in lexicographical order, so when we request the next flight, we always get the one to the alphabetically smallest airport.
The core of the algorithm is a recursive function, let's call it dfs, that performs a post-order traversal of the graph. We start the traversal from "JFK". For a given airport, the dfs function iterates through all its outgoing flights. It does this by polling from the airport's priority queue, which removes the flight and ensures we don't use it again. For each flight, it makes a recursive call to dfs with the destination airport.
Once the dfs function has exhausted all outgoing flights from an airport (the priority queue for that airport becomes empty), it adds that airport to the front of the result list. This is the crucial step of Hierholzer's algorithm. The first airport to be added to the list is the final destination of the itinerary. The starting airport, "JFK", will be the last to have its dfs call complete, so it will be added last to the front of the list, correctly placing it at the beginning of the itinerary.
class Solution { // Adjacency list using a PriorityQueue to handle lexical order private Map<String, PriorityQueue<String>> adj = new HashMap<>(); // The final itinerary, built backwards private LinkedList<String> itinerary = new LinkedList<>(); public List<String> findItinerary(List<List<String>> tickets) { // Build the graph for (List<String> ticket : tickets) { String from = ticket.get(0); String to = ticket.get(1); adj.computeIfAbsent(from, k -> new PriorityQueue<>()).add(to); } // Start the DFS-like traversal from "JFK" dfs("JFK"); return itinerary; } private void dfs(String airport) { // Visit all the destinations from the current airport PriorityQueue<String> destinations = adj.get(airport); while (destinations != null && !destinations.isEmpty()) { // Poll the next destination to visit it and remove the edge String nextAirport = destinations.poll(); dfs(nextAirport); } // Add the airport to the front of the list after visiting all its destinations itinerary.addFirst(airport); }}Complexity
Time
O(E log E), where E is the number of tickets. Building the graph takes O(E log d_max) where d_max is the max out-degree, bounded by O(E log E). The traversal visits each edge once, and each visit involves a `poll` operation from a priority queue, taking O(log d) time. The total time is dominated by these operations.
Space
O(V + E), where V is the number of unique airports and E is the number of tickets. This space is for the adjacency list, the recursion stack, and the result list.
Trade-offs
Pros
Very efficient and is the standard algorithm for finding Eulerian paths.
Correctly and elegantly finds the lexicographically smallest itinerary without expensive backtracking.
Guaranteed to find a solution since the problem statement ensures one exists.
Cons
The post-order traversal logic for building the path backward can be less intuitive than a direct path-building approach.
Solutions
Solution
class Solution { void dfs(Map<String, Queue<String>> adjLists, List<String> ans, String curr) { Queue<String> neighbors = adjLists.get(curr); if (neighbors == null) { ans.add(curr); return; } while (!neighbors.isEmpty()) { String neighbor = neighbors.poll(); dfs(adjLists, ans, neighbor); } ans.add(curr); return; }public List<String> findItinerary(List<List<String>> tickets) { Map<String, Queue<String>> adjLists = new HashMap<>(); for (List<String> ticket : tickets) { String from = ticket.get(0); String to = ticket.get(1); if (!adjLists.containsKey(from)) { adjLists.put(from, new PriorityQueue<>()); } adjLists.get(from).add(to); } List<String> ans = new ArrayList<>(); dfs(adjLists, ans, "JFK"); Collections.reverse(ans); return ans; }}class Solution {public: vector<string> findItinerary(vector<vector<string>> &tickets) { unordered_map<string, priority_queue<string, vector<string>, greater<string>>> g; vector<string> ret;class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: graph = defaultdict(list) for src, dst in sorted(tickets, reverse=True): graph[src]. append(dst) itinerary = [] def dfs(airport): while graph[airport]: dfs(graph[airport]. pop()) itinerary . append(airport) dfs("JFK") return itinerary[:: - 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.