Is Reconstruct Itinerary easy or hard?

Reconstruct Itinerary is classified as a hard problem because it requires recognizing the Eulerian path structure in a directed graph. The challenge comes from combining graph traversal, lexical ordering, and postorder route construction.

Reconstruct Itinerary Python/Java solution

Python and Java implementations usually build a map from airport to a priority queue or sorted list of destinations. DFS then repeatedly removes the smallest destination edge and appends airports to the route when no outgoing edges remain. The resulting list is reversed to produce the final itinerary.

How to solve Reconstruct Itinerary in O(n)?

Pure O(n) is difficult because the destinations must be ordered lexicographically. Most optimal solutions run in O(E log E) due to sorting adjacency lists. After sorting, Hierholzer's DFS visits each edge once, giving linear traversal over the graph structure.

What is the best approach for Reconstruct Itinerary?

Hierholzer's Algorithm for Eulerian paths is the best approach. The tickets form a directed graph where each edge must be used exactly once. Using DFS with lexicographically ordered adjacency lists constructs the Eulerian path while ensuring the smallest lexical itinerary. The overall complexity is O(E log E).

Is Reconstruct Itinerary asked at Google/Amazon/Meta?

Reconstruct Itinerary appears in interviews that test graph traversal and Eulerian path knowledge. Variants of this problem have been reported in interviews at companies like Amazon, Google, and Meta because it combines graph modeling, DFS, and lexical ordering constraints.

What data structure is used in Reconstruct Itinerary?

The core data structure is an adjacency list representing the directed graph of flights. Destinations are typically stored in a min-heap or sorted list to guarantee lexical order. A recursion stack or explicit stack is used during DFS traversal.

What is the time complexity of Reconstruct Itinerary?

The typical solution runs in O(E log E) time, where E is the number of tickets. The log factor comes from sorting destinations or maintaining a min-heap for lexical ordering. The DFS traversal itself processes each edge exactly once.

Description Solution Video 17:38

332. Reconstruct Itinerary

Hard45.0% acceptance23 companies

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.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Constraints: