332. Reconstruct Itinerary - Detailed Explanation

Problem Statement

You are given a list of airline tickets represented by pairs of departure and arrival airports [from, to]. The task is to reconstruct the itinerary in order. All of the tickets belong to a man who departs from "JFK". Thus, the itinerary must begin with "JFK".

Key Points:

• All tickets must be used exactly once.
• If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

Example 1:
Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Explanation: Starting from JFK, the itinerary goes to MUC, then LHR, SFO, and finally SJC.

Example 2:
Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Although there are multiple ways to reconstruct the itinerary, the itinerary ["JFK","ATL","JFK","SFO","ATL","SFO"] has the smallest lexical order when compared to alternatives.

Example 3:
Input: [["JFK","A"],["A","B"],["B","JFK"],["JFK","C"]]
Output: ["JFK","A","B","JFK","C"]
Explanation: Start at JFK, follow the tickets to A, then B, back to JFK, and finally to C.

Constraints:

• The number of tickets is in the range [1, 300].
• The airports are represented by three capital letters (IATA codes).
• It is guaranteed that all tickets form at least one valid itinerary.

Hints to Get Started

1. Graph Representation:
   Think about representing the tickets as a graph where each airport is a node and each ticket is a directed edge from the departure to the destination airport.

2. Traversal Strategy:
   Consider how you would perform a depth-first search (DFS) on this graph. How might you backtrack once you’ve reached a dead end?

3. Lexical Order:
   Since multiple itineraries may be possible, you must always choose the smallest lexical destination when faced with a choice. Sorting the list of destinations for each departure node might be useful.

Approach 1: Brute Force (Backtracking)

Explanation

A brute force method would try every possible permutation of the tickets to see which sequence forms a valid itinerary starting from "JFK". You would:

• Use each ticket exactly once.
• Check every possible path until you have used all tickets.
• Keep track of the valid itineraries and finally return the one with the smallest lexical order.

Step-by-Step Walkthrough

1. Graph Construction: Build a graph where the key is the departure airport and the value is a list of destination airports.

2. Backtracking DFS:

   • Start at "JFK".
   • At each step, iterate over the possible destinations.
   • Mark the ticket as used and recursively attempt to build the itinerary.
   • Backtrack if you hit a dead end (i.e., not all tickets are used).

3. Lexical Order: After collecting all valid itineraries, compare them and return the smallest lexical order sequence.

Complexity Analysis

• Time Complexity: The brute force method could potentially try all permutations of tickets, leading to a worst-case time complexity of O(n!) where n is the number of tickets.
• Space Complexity: O(n) for the recursion call stack and storage of itinerary.

Drawbacks

• The brute force solution is not practical for larger inputs due to its exponential time complexity.

Approach 2: Optimal (Hierholzer’s Algorithm / DFS with Lexical Ordering)

Explanation

The optimal solution leverages a modified depth-first search (DFS) that is inspired by Hierholzer’s algorithm for finding an Eulerian path in a graph:

• Graph Construction:
  Build a graph (using a hash map/dictionary) where each departure airport maps to a min-heap (or sorted list) of arrival airports. This ensures that when you have multiple choices, you always pick the airport with the smallest lexical order.

• DFS Traversal:
  Recursively visit airports using the available tickets. Once you exhaust the destinations from a given airport, add the airport to the itinerary. Since this process effectively records the itinerary in reverse order, you will need to reverse the list at the end.

• Correctness:
  By following the DFS and always choosing the smallest lexical option, the algorithm guarantees that the final itinerary is both valid (using all tickets exactly once) and lexically smallest.

Step-by-Step Walkthrough

1. Graph Construction:

   • Create a dictionary where each key is an airport and each value is a list (or priority queue) of destination airports.

   • Sort the destinations for each departure in reverse order (if using a list) so that you can efficiently pop the last element (which is the smallest lexicographically).

2. Recursive DFS Function:

   • Start the DFS from "JFK".

   • While there are destinations available from the current airport, recursively call DFS on the next airport.

   • Append the current airport to the itinerary list when no further destinations can be visited.

3. Final Itinerary:
   • Since the airports are added in reverse order during the DFS, reverse the itinerary list to obtain the final answer.

Complexity Analysis

• Time Complexity:
  • Graph construction takes O(n log n) due to sorting the destinations.
  • DFS traversal takes O(n) since each ticket is used exactly once.
• Space Complexity: O(n) for the recursion stack and the graph storage.

Code Implementation

Python Code