Reconstruct Flight Path
Problem Statement
You are given a list of flight tickets tickets
where tickets[i] = [from_i, to_i]
represent the source airport and the destination airport.
Each from_i
and to_i
consists of three uppercase English letters.
Reconstruct the itinerary in order and return it.
All of the tickets belong to someone who originally departed from "JFK"
. Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once.
If there are multiple valid flight paths, return the lexicographically smallest one.
- For example, the itinerary
["JFK", "SEA"]
has a smaller lexical order than["JFK", "SFO"]
.
You may assume all the tickets form at least one valid flight path.
Example 1:
Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]]
Output: ["JFK","BUF","HOU","SEA"]
Example 2:
Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]
Output: ["JFK","HOU","JFK","SEA","JFK"]
Explanation: Another possible reconstruction is ["JFK","SEA","JFK","HOU","JFK"]
but it is lexicographically larger.
Constraints:
1 <= tickets.length <= 300
from_i != to_i
You should aim for a solution with O(E \log E)
time and O(E)
space, where E
is the number of tickets (edges).
Recommended Time and Space Complexity
You should aim for a solution with O(E \log E)
time and O(E)
space, where E
is the number of tickets (edges).
Hint 1
Consider this problem as a graph where airports are the nodes and tickets are the edges. Since we need to utilize all the tickets exactly once, can you think of an algorithm that visits every edge exactly once? Additionally, how do you ensure the smallest lexical order is maintained?
Hint 2
We build an adjacency list from the given tickets, which represent directed edges. We perform a DFS to construct the result, but we first sort the neighbors’ list of each node to ensure the smallest lexical order. Why? Sorting guarantees that during DFS, we visit the node with the smallest lexical order first.
Hint 3
DFS would be a naive solution, as it takes O(E * V)
time, where E
is the number of tickets (edges) and V
is the number of airports (nodes). In this approach, we traverse from the given source airport JFK
, perform DFS by removing the neighbor, traversing it, and then reinserting it back. Can you think of a better way? Perhaps an advanced algorithm that incorporates DFS might be helpful?
Hint 4
We can use Hierholzer’s algorithm, a modified DFS approach. Instead of appending the node to the result list immediately, we first visit all its neighbors. This results in a post-order traversal. After completing all the DFS calls, we reverse the path to obtain the final path, which is also called Euler’s path.
Solution
Depth First Search
def find_itinerary(tickets: list[list[str]]) -> list[str]: adj = {src: [] for src, dst in tickets} tickets.sort() for src, dst in tickets: adj[src].append(dst)
res = ["JFK"]
def dfs(src): if len(res) == len(tickets) + 1: return True if src not in adj: return False
temp = list(adj[src]) for i, v in enumerate(temp): adj[src].pop(i) res.append(v) if dfs(v): return True adj[src].insert(i, v) res.pop() return False
dfs("JFK") return res
Time complexity: O(E * V)
Space complexity: O(E * V)