Reconstruct Itinerary

Problem Description

You are given a list of airline tickets where tickets[i] = [from_i, to_i] 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. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Key Insights

• The problem involves reconstructing a path through a directed graph where each node represents an airport.
• Each ticket can be viewed as a directed edge from one airport to another.
• To ensure the smallest lexical order, we can use a lexicographically sorted structure to store the destinations for each airport.
• An Eulerian path exists since all tickets must be used exactly once, allowing us to traverse the graph.

Space and Time Complexity

Time Complexity: O(E log E), where E is the number of tickets (edges). Sorting the destinations takes O(E log E). Space Complexity: O(V + E), where V is the number of airports (vertices) and E is the number of tickets.

Solution

To solve the problem, we can use Depth-First Search (DFS) along with a graph representation using an adjacency list. The adjacency list will store the destinations for each airport in a sorted manner to facilitate the traversal in lexical order. The algorithm follows these steps:

1. Build the graph using a dictionary of lists, where the keys are the departure airports and the values are sorted lists of arrival airports.
2. Perform a DFS starting from "JFK". As we traverse, we will keep track of the itinerary in reverse order to ensure we can construct it correctly at the end.
3. Backtrack whenever we reach a dead end by removing the last airport from our itinerary.
4. Finally, reverse the itinerary to get the correct order.

Code Solutions