Solution: Reconstruct Itinerary
Let’s solve the Reconstruct Itinerary problem using the Graph Algo pattern.
We'll cover the following
Statement
Given a list of airline tickets
where tickets[i] = [from
i
, to
i
]
represent a departure airport and an arrival airport of a single flight, reconstruct the itinerary in the correct order and return it.
The person who owns these tickets
always starts their journey from "JFK"
. Therefore, the itinerary must begin with "JFK"
. If there are multiple valid itineraries, you should prioritize the one with the smallest
For example, the itinerary
["JFK", "EDU"]
has a smaller lexical order than["JFK", "EDX"]
.
Note: You may assume all tickets form at least one valid itinerary. You must use all the tickets exactly once.
Constraints:
tickets.length
tickets[i].length
from
i
.length
to
i
.length
from
i
to
i
from
i
andto
i
consist of uppercase English letters.
Solution
The algorithm uses “JFK”
. Hierholzer’s algorithm is great for finding Eulerian paths and cycles, which is why we use it here.
To further understand an Eulerian cycle and how to find one with Hierholzer’s algorithm, please review this Answer on “Finding the Eulerian Cycle with Hierholzer’s Algorithm.”
The algorithm starts by arranging the destinations in reverse lexicographical order to ensure we always choose the smallest destination first. It then uses depth-first search (DFS) starting from “JFK”
to navigate the flights. As it explores each flight path, it builds the itinerary by appending each visited airport when there are no more destinations to visit from that airport. Since the airports are added in reverse order during this process, the final step is to reverse the list to get the correct itinerary.
The basic algorithm to solve this problem will be:
Create a dictionary,
flightMap
, to store the flight information. Each key represents an airport; its corresponding value is a list of destinations from that airport.Initialize an empty list,
result
, to store the reconstructed itinerary.Sort the destinations lexicographically in reverse order to ensure that the smallest destination is chosen first.
Perform DFS traversal starting from the airport
"JFK"
.Get the list of
destinations
for the current airport fromflightMap
.While there are
destinations
available:Pop the
nextDestination
fromdestinations
.Recursively explore all available flights starting from the popped
nextDestination
, until all possible flights have been considered.
Append the
current
airport to theresult
list.
Return the
result
list in reverse order to ensure the itinerary starts from the initial airport,"JFK"
, and proceeds through the subsequent airports in the correct order.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.