Reconstruct Itinerary
Asked at Netflix
Problem
Given a list of airline tickets as pairs [from, to], reconstruct the itinerary in order. All tickets must be used exactly once, and the itinerary must begin with JFK. If multiple valid itineraries exist, return the lexicographically smallest one.
Asked At
| Company | Difficulty | |
|---|---|---|
| Netflix | HARD | View all Netflix questions → |
How to Think About It
Model the problem as a directed multigraph where airports are nodes and tickets are edges.
The problem asks for an Eulerian path starting at JFK that uses every edge exactly once.
Use Hierholzer algorithm: DFS greedily visiting neighbors in sorted order.
Sort adjacency lists so the smallest destination is visited first for lexicographic order.
Backtrack edges only after exhausting all outgoing edges from a node to build the path in reverse.
Optimal Approach
Build an adjacency list mapping each airport to its destinations, sorting destinations lexicographically. Use Hierholzer algorithm to find the Eulerian path: start from JFK, recursively visit the smallest unvisited destination, and push airports to the result stack after exhausting all edges. Since adjacency lists are sorted, the first complete path found is lexicographically smallest. Reverse the result to get the correct itinerary order. Time complexity is O(E log E) for sorting edges and O(E) for the traversal.
What Trips People Up in Real Interviews
Clarify that all tickets must be used exactly once (Eulerian path requirement).
Explain why sorting adjacency lists lexicographically ensures the smallest itinerary.
Discuss Hierholzer algorithm as the standard approach for Eulerian paths.
Mention that using a multiset or list removal handles duplicate tickets correctly.
Address why reversing the result at the end gives the correct order.
Solution Code
class Solution:
def findItinerary(self, tickets: list[list[str]]) -> list[str]:
from collections import defaultdict
graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
result = []
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop())
result.append(airport)
dfs('JFK')
return result[::-1]Frequently Asked Questions
What is the Reconstruct Itinerary problem?
Given a list of airline tickets as pairs [from, to], reconstruct the itinerary in order. All tickets must be used exactly once, and the itinerary must begin with JFK. If multiple valid itineraries exist, return the lexicographically smallest one.
How do you solve Reconstruct Itinerary?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Reconstruct Itinerary?
Reconstruct Itinerary is asked at Netflix. It is a hard difficulty problem.
What are common mistakes on Reconstruct Itinerary?
- Clarify that all tickets must be used exactly once (Eulerian path requirement).
- Explain why sorting adjacency lists lexicographically ensures the smallest itinerary.
- Discuss Hierholzer algorithm as the standard approach for Eulerian paths.
- Mention that using a multiset or list removal handles duplicate tickets correctly.
- Address why reversing the result at the end gives the correct order.