Reconstruct Itinerary
Problem Description
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 <= 300
- tickets[i].length == 2
- fromi.length == 3
- toi.length == 3
- fromi and toi consist of uppercase English letters.
- fromi != toi
Solve it on LeetCode
Approaches
1. Hierholzer’s Algorithm with DFS (Backtracking)
Hierholzer’s algorithm is a method to find an Eulerian path or cycle (a path or cycle that visits every edge exactly once) in a graph. Since the given problem is about reconstructing an itinerary that visits all flights (edges) exactly once, and starts from "JFK", we can use this approach directly.
The idea behind Hierholzer’s algorithm in this context is:
- Start from "JFK" and greedily visit the lexicographically smallest destination city, marking that flight as "used".
- Use Depth-First Search (DFS) to explore each destination and backtrack when there are no further cities to visit from the current city.
- Append the current city to a route list when you can no longer move forward (i.e., dead-end).
Steps:
- Use a priority queue (a min-heap) to keep the adjacency list for each airport. This ensures the lexicographical order in flight selection.
- Perform a DFS recursively to explore the itinerary starting from "JFK".
- Append the current airport to the itinerary only when a dead-end is reached and all flights are utilized from the current airport.
- Reverse the itinerary at the end to get the correct order.
Code:
- Time Complexity: O(E logV) time, where E is the number of edges (tickets) and V is the number of vertices (airports). This is because for each airport, we may sort its list of destinations (inserting each destination into a priority queue which takes logV time).
- Space Complexity: O(V + E) as we need to store the graph (connections between airports) and the list of destinations for each airport.
2. Hierholzer’s Algorithm with Iterative DFS (Using Stack)
Instead of performing the DFS recursively, this approach uses a stack to iteratively perform DFS. The principle remains the same—ensure all edges are visited exactly once, storing the itinerary in a reverse manner and then reversing it at the end.
Steps:
- Utilize a stack to simulate the DFS process.
- Start with pushing "JFK" onto the stack.
- While there are nodes to explore until the stack is empty:
- Look at the top of the stack to get the current airport.
- If there are outgoing flights from this airport, move to the lexicographically smallest airport using that flight.
- If no flights left, add this airport to the route and pop from the stack.
- Reverse the itinerary list to construct the final itinerary correctly.
Code:
- Time Complexity: O(E logV), given that each airport's priority queue operations require logV time.
- Space Complexity: O(V + E) to store each airport’s destinations and stack operations.