Problem Statement

Reconstruct Itinerary

You are given a list of plane tickets. Each ticket looks like [from, to], which means "this ticket lets you fly from one airport to another." You have to use every single ticket exactly once and put them in order to form one trip that always starts at JFK. Think of the tickets as a pile of arrows between airports, and your job is to walk through all the arrows, using each arrow one time, ending up with the full route. Sometimes more than one route is possible. When that happens, pick the one that comes first in alphabetical order (so a route starting JFK to ATL beats one starting JFK to SFO, because "ATL" comes before "SFO"). The tool that fits this is a stack plus a depth-first search. A stack is like a pile of plates: you add a plate to the top and you take a plate off the top, so the last one you put on is the first one you take off. Depth-first search (DFS) just means "keep walking forward as far as you can before turning back." Together this is called Hierholzer's algorithm, a standard way to walk every edge of a graph once.

hardGraphDFSGraphsTime: O(E log E) · Space: O(V+E)

Signals to notice

use all tickets exactly oncefind Eulerian pathlexicographically smallest itinerary

Brute force first

Try all permutations of tickets — O(n!). Each ordering checked for validity.

The key insight

Hierholzer's algorithm: DFS greedily choosing the lexicographically smallest neighbor. When stuck, add the current airport to the result in reverse. O(E log E) for sorting adjacency lists.

Trace it on `tickets=[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]`

build: sorted-reverse fills graph so each list pops smallest-first -> graph[JFK]=[NRT,KUL], graph[NRT]=[JFK]; stack=[JFK], result=[]
top=JFK, graph[JFK] nonempty -> pop KUL; stack=[JFK,KUL], graph[JFK]=[NRT]
top=KUL, graph[KUL] empty -> backtrack: result=[KUL], stack=[JFK]
top=JFK, graph[JFK] nonempty -> pop NRT; stack=[JFK,NRT], graph[JFK]=[]
top=NRT, graph[NRT] nonempty -> pop JFK; stack=[JFK,NRT,JFK], graph[NRT]=[]
top=JFK, graph[JFK] empty -> backtrack: result=[KUL,JFK]; then NRT empty -> result=[KUL,JFK,NRT]; then JFK empty -> result=[KUL,JFK,NRT,JFK]; stack=[]
stack empty -> return reversed(result) = [JFK,NRT,JFK,KUL]

What must stay true

By always choosing the smallest destination and building the result when backtracking (stuck = no more edges), you construct the lexicographically smallest Eulerian path in reverse.

Shape of the loop

build graph: for src,dst in sorted(tickets, reverse): graph[src].append(dst)
stack=[start], result=[]
while stack:
  while graph[stack[-1]] not empty: stack.push(graph[stack[-1]].pop())   // dive to dead end
  result.append(stack.pop())                                            // backtrack -> record
return reversed(result)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not building the result in reverse — Hierholzer's adds cities when backtracking from dead ends, so the path is assembled from the end backward.

Graphs Pattern