Skip to main content
Talentd

Reconstruct Itinerary - Solution & Explanation

HardDepth-First SearchGraphEulerian Circuit11 min readAsked at: Amazon, Microsoft, Apple +20
Practice this problem

Problem Statement

You are given a list of airline tickets where tickets[i] = [fromi, toi] 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:

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi and toi consist of uppercase English letters.
  • fromi != toi

Approach Overview

Problem Overview: You receive a list of airline tickets where each ticket represents a directed edge [from, to]. Starting from "JFK", reconstruct the full travel itinerary that uses every ticket exactly once. If multiple valid routes exist, return the itinerary with the smallest lexical order.

The key observation: every ticket must be used exactly once, which turns the problem into finding an Eulerian path in a directed graph. Airports are nodes, tickets are edges. The itinerary is the path that visits every edge exactly once while respecting lexical ordering.

Approach 1: Hierholzer's Algorithm for Eulerian Path (O(E log E) time, O(E) space)

Model the tickets as a directed graph using an adjacency list. Because the itinerary must be lexicographically smallest, store each airport's destinations in sorted order (often implemented with a min-heap or reversed sorted list). Then run a depth-first traversal based on Hierholzer's algorithm. The DFS always takes the smallest available destination and removes that edge from the graph. When a node has no remaining outgoing edges, append it to the route. This naturally builds the itinerary in reverse order, so the final answer is reversed at the end. The algorithm works because Eulerian paths are constructed by exploring edges until a dead end, then backtracking while stitching partial circuits together. This is the most common interview solution and directly leverages concepts from graph traversal and Depth-First Search. Time complexity is O(E log E) due to sorting or heap operations, and space complexity is O(E) for the adjacency structure and recursion stack.

Approach 2: Iterative Stack-based Simulation (O(E log E) time, O(E) space)

This approach implements the same Eulerian path construction but avoids recursion. Instead of recursive DFS, maintain an explicit stack starting with "JFK". While the airport at the top of the stack still has outgoing flights, push the smallest destination onto the stack and remove that edge from the adjacency list. When an airport has no remaining outgoing edges, pop it from the stack and append it to the itinerary. This mimics the postorder behavior of DFS and constructs the path in reverse order, just like Hierholzer's algorithm. The iterative approach is useful in environments where recursion depth might be limited and gives more explicit control over the traversal state. The complexity remains O(E log E) time and O(E) space because edge ordering is still required.

Recommended for interviews: The Hierholzer DFS approach is what most interviewers expect because the problem is essentially an Eulerian path construction with lexical ordering. Showing that you recognize the graph structure and apply Hierholzer's algorithm demonstrates strong algorithmic understanding. The iterative stack version is a good follow-up optimization that shows you understand how DFS traversal works internally.

Approach 1: Approach 1: Hierholzer's Algorithm for Eulerian Path

Approach Description: Hierholzer's algorithm helps find the Eulerian path in a graph. The key idea is to keep backtracking and viewing if there's another unexplored path. We start from the node 'JFK' and explore possible destinations using DFS while following lexical order to ensure the smallest lexical itinerary.

This solution creates a graph where each key is a departure point and the value is a list of destinations sorted in lexical order.

We use a stack to track the journey from 'JFK'. For each node, we explore its destinations until we exhaust all paths, appending each node to our result list in the order we backtrack. Finally, we reverse the result path to get the correct itinerary.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N log N) where N is the number of tickets, due to sorting.
Space Complexity: O(N) to store the graph and the route.

Try this approach in the editor →

Approach 2: Approach 2: Iterative Stack-based Simulation

Approach Description: Another way to simulate the backtracking approach is using an iterative stack to push/pop airports while ensuring that we appropriately capture our path by focusing on edge traversal.

Using a map of priority queues, this C++ code builds a graph of tickets. The stack represents the ongoing traversal through JFK and beyond, continually adding destinations in lexically sorted order. The itinerary is completed by backtracking through available flights, culminating in a reversed route list.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(N log N) due to priority queue operations.
Space Complexity: O(N) for storing the graph and itinerary.

Try this approach in the editor →

Approach 3: Eulerian Path

The problem is essentially about finding a path that starts from a specified starting point, passes through all the edges exactly once, and has the smallest lexicographical order among all such paths, given n vertices and m edges. This is a classic Eulerian path problem.

Since the problem guarantees that there is at least one feasible itinerary, we can directly use the Hierholzer algorithm to output the Eulerian path starting from the starting point.

The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the number of edges.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Hierholzer's Algorithm for Eulerian Path

Time Complexity: O(N log N) where N is the number of tickets, due to sorting.
Space Complexity: O(N) to store the graph and the route.

Approach 2: Iterative Stack-based Simulation

Time Complexity: O(N log N) due to priority queue operations.
Space Complexity: O(N) for storing the graph and itinerary.

Eulerian Path—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hierholzer's Algorithm with DFSO(E log E)O(E)Best general solution. Clean implementation and commonly expected in interviews.
Iterative Stack-based SimulationO(E log E)O(E)Useful when avoiding recursion or when implementing DFS traversal explicitly.

Video Solution

Reconstruct Itinerary - Leetcode 332 - Python • NeetCode • 122,530 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Reconstruct Itinerary with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Common Subpath

Next

Valid Arrangement of Pairs