HardArrayStringDepth-First SearchGraphSortingHeapEulerian CircuitEulerian PathUpdated Sep 2026

332. Reconstruct Itinerary

Asked at Netflix, Pinterest

Difficulty

Hard

Time

O(E log E)

Space

O(E)

Pattern

Array

Companies

2

Problem

You get a list of flight tickets. Each ticket is a pair [from, to] — the airport you leave and the airport you land at. All these tickets belong to one trip, and the trip starts at "JFK".

Your job is to put all the tickets in one order so that the arrival airport of each ticket is the departure airport of the next one. Every ticket must be used exactly once. The itinerary starts with "JFK", so the returned list has one more airport than the number of tickets.

Sometimes more than one valid order exists. In that case, return the one that is smallest when you read the whole list as a single string (lexicographic order). For example, ["JFK", "LGA"] is smaller than ["JFK", "LGB"] because A comes before B. You may assume at least one valid itinerary always exists.

Tickets are edges in a graph

JFK → MUCMUC → LHRLHR → SFOSFO → SJCThe four tickets chain together into one path from JFKto SJC.itineraryJFKMUCLHRSFOSJC01234The answer has 5 airports: one start plus one perticket.
Each ticket is a directed edge. We must walk every edge exactly once, starting at JFK.

Constraints

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

Examples

Example 1
Inputtickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output["JFK","MUC","LHR","SFO","SJC"]
WhyStart at JFK. The only ticket leaving JFK goes to MUC, then MUC → LHR, then LHR → SFO, then SFO → SJC. Every ticket is used once and the chain never breaks, so this is the only valid itinerary.
Example 2
Inputtickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output["JFK","ATL","JFK","SFO","ATL","SFO"]
WhyTwo itineraries are possible. The other one is ["JFK","SFO","ATL","JFK","ATL","SFO"]. Compare them position by position: both start with JFK, but the second airport is ATL in the answer and SFO in the other one. ATL is smaller, so the answer wins.

Asked At

2 companies
CompanyDifficulty
NetflixHardView all Netflix questions →
PinterestHardView all Pinterest questions →

How to Think About It

1

Model the problem as a directed multigraph where airports are nodes and tickets are edges.

2

The problem asks for an Eulerian path starting at JFK that uses every edge exactly once.

3

Use Hierholzer algorithm: DFS greedily visiting neighbors in sorted order.

4

Sort adjacency lists so the smallest destination is visited first for lexicographic order.

5

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.

Hierholzer: DFS then reverse

adjacency (sorted)JFKATLSFOJFKATL, SFOATLJFK, SFOSFOATLDestinations are sorted, so JFK tries ATL before SFO.result (built backwards)SFOATLSFOJFKATLJFKfrontbackAirports are pushed when they run out of tickets, so the path comesout in reverse.answerJFKATLJFKSFOATLSFO012345Reversing the stack gives the lexicographically smallest itinerary.while graph[node]: dfs(smallest next)push node when no tickets remainreturn reversed(result)
We always take the smallest unused ticket. When a node has no tickets left, we add it to the result. Reversing gives the itinerary.
ComplexityTime O(E log E)Space O(E)Sorting the E tickets costs O(E log E), and the DFS visits each edge once for O(E); the graph and the result list each hold O(E) items.

What Trips People Up in Real Interviews

1

Clarify that all tickets must be used exactly once (Eulerian path requirement).

2

Explain why sorting adjacency lists lexicographically ensures the smallest itinerary.

3

Discuss Hierholzer algorithm as the standard approach for Eulerian paths.

4

Mention that using a multiset or list removal handles duplicate tickets correctly.

5

Address why reversing the result at the end gives the correct order.

Solution Code

O(E log E) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(E log E) time and O(E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Reconstruct Itinerary?

Reconstruct Itinerary is asked at Netflix, Pinterest. 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.