# 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 leastone valid itinerary. You must use all the tickets exactly once.

**Constraints:**

$1 \leq$ `tickets.length`

$\leq 300$ `tickets[i].length`

$= 2$ `from`

_{i}`.length`

$= 3$ `to`

_{i}`.length`

$= 3$ `from`

_{i}$\neq$ `to`

_{i}`from`

_{i}and`to`

_{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 from`flightMap`

.While there are

`destinations`

available:Pop the

`nextDestination`

from`destinations`

.Recursively explore all available flights starting from the popped

`nextDestination`

, until all possible flights have been considered.

Append the

`current`

airport to the`result`

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.