Problem Description
Given a list of airline tickets represented as [from, to] pairs, reconstruct the itinerary such that:
- The itinerary begins with "JFK".
- Every ticket is used exactly once.
- If multiple valid itineraries exist, return the one with the smallest lexical order when concatenated as a single string.
Key Insights
- Model the tickets as a directed graph where airports are nodes.
- The problem is akin to finding an Eulerian path through the graph.
- Use Depth-First Search (DFS) with Hierholzer’s algorithm to construct the itinerary.
- To ensure lexical order, sort the destination lists in reverse order so that the smallest lexical destination can be popped during DFS.
- Build the itinerary in reverse during backtracking and then reverse it to get the final order.
Space and Time Complexity
Time Complexity: O(E log E), where E is the number of tickets, due to the sorting of edges. Space Complexity: O(E), to store the graph and recursion stack.
Solution
Construct an adjacency list (graph) mapping each departure airport to a list of destination airports sorted in reverse lexicographical order. Perform DFS starting from "JFK". During DFS, traverse while there are destinations available from the current airport. Append airports to the itinerary as you backtrack. Reverse the built itinerary at the end to obtain the correct order.