Skip to main content

332. Reconstruct Itinerary

hard

Given a list of airline tickets, reconstruct the lexicographically smallest itinerary that uses every ticket exactly once, starting from 'JFK'. The textbook Eulerian path problem — Hierholzer's algorithm with a min-heap for tie-breaking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

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

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use every edge exactly once + return to a connected traversal = Eulerian path. Tickets are edges, airports are nodes.

Hint 2

Greedy DFS that always picks the lex-smallest unused outgoing edge sometimes paints you into a corner. How do you recover?

Hint 3

Hierholzer's algorithm: DFS deeply on the lex-smallest neighbor; when stuck, append the current node to the answer and backtrack. Reverse the answer at the end.

Solution approach

Reveal approach

Hierholzer's algorithm for Eulerian path. Build an adjacency list where each airport maps to a min-heap of destinations (so we always extract the lex-smallest next). DFS from JFK: while the heap at the current airport is non-empty, pop the smallest destination and recurse into it. When the heap is empty (dead end), prepend the current airport to the answer (or append + reverse at the end). The trick: a greedy 'always go lex-smallest' DFS can leave unused edges; Hierholzer fixes this by post-order appending — dead-ends get appended first and end up at the END of the reversed answer, while nodes still having alternative paths get appended later and end up earlier. Because the problem guarantees at least one valid itinerary, every edge will be consumed. O((V + E) log E) time for the heap operations, O(V + E) space.

Complexity

Time
O((V + E) log E)
Space
O(V + E)

Related patterns

  • graph-dfs
  • eulerian-path
  • hierholzers
  • heap

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Reconstruct Itinerary and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →