332. Reconstruct Itinerary

At a Glance

Topic: graphs
Pattern: Hierholzer’s algorithm (Eulerian circuit / trail) with DFS postorder
Difficulty: Hard
Companies: Google, Amazon, Meta, Bloomberg, Indeed
Frequency: Medium
LeetCode: 332

Given airline tickets [from, to] (multiset), reconstruct lexicographically smallest itinerary starting at "JFK" that uses every ticket exactly once. Assume at least one valid itinerary exists.

Recognition Cues

Use each edge exactly once — Eulerian trail on directed multigraph
“Smallest lex order” — when multiple Eulerian trails exist, defer larger neighbors in DFS (postorder / reverse stack)
Start fixed at JFK

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Backtracking — try all permutations — factorial — too slow.
Hierholzer + adjacency sorted — peel edges lazily; append airport after exhausting outgoing — O(E log E) for sorting — optimal.

Optimal Solution

Go

import "sort"

func findItinerary(tickets [][]string) []string {
	adjacency := make(map[string][]string)
	for _, ticket := range tickets {
		from := ticket[0]
		to := ticket[1]
		adjacency[from] = append(adjacency[from], to)
	}
	for airport := range adjacency {
		sort.Slice(adjacency[airport], func(indexA, indexB int) bool {
			return adjacency[airport][indexA] > adjacency[airport][indexB]
		})
	}
	itinerary := []string{}
	var visit func(airport string)
	visit = func(airport string) {
		for len(adjacency[airport]) > 0 {
			nextCount := len(adjacency[airport])
			nextAirport := adjacency[airport][nextCount-1]
			adjacency[airport] = adjacency[airport][:nextCount-1]
			visit(nextAirport)
		}
		itinerary = append(itinerary, airport)
	}
	visit("JFK")
	left := 0
	right := len(itinerary) - 1
	for left < right {
		itinerary[left], itinerary[right] = itinerary[right], itinerary[left]
		left++
		right--
	}
	return itinerary
}

JavaScript

function findItinerary(tickets) {
  const adjacency = new Map();
  for (const [from, to] of tickets) {
    if (!adjacency.has(from)) {
      adjacency.set(from, []);
    }
    adjacency.get(from).push(to);
  }
  for (const destinations of adjacency.values()) {
    destinations.sort((left, right) => (left > right ? -1 : left < right ? 1 : 0));
  }
  const itinerary = [];
  function visit(airport) {
    const destinations = adjacency.get(airport);
    while (destinations && destinations.length > 0) {
      const nextAirport = destinations.pop();
      visit(nextAirport);
    }
    itinerary.push(airport);
  }
  visit('JFK');
  return itinerary.reverse();
}

Walkthrough

Tickets JFK->SFO, JFK->ATL, SFO->ATL, ATL->JFK, ATL->SFO. Sort each list descending so pop yields lex smallest first. DFS from JFK: consume edge to ATL before SFO when popping from reversed-sorted slice—actually desc sort means last index is smallest; we pop from end = smallest. Hierholzer builds postorder; reverse gives itinerary.

Invariant: When visit returns from an airport, all outgoing edges from that node are consumed — standard Eulerian peel.

Edge Cases

Single ticket JFK->X — [JFK, X]
Dead-end airports with no outgoing (leaf) — handled when stack unwinds
Multiple parallel tickets same route — multiset; adjacency list holds duplicates

Pitfalls

Lex order requires processing smallest destination first — implement via reverse sort + pop or forward sort + shift from front (costlier)
Building full itinerary forward greedily without Hierholzer — can strand unused edges

Variants

Verify Eulerian trail exists before constructing — in-degree/out-degree balance except endpoints.
Max edges / weighted ticket preference — priority overrides lex tie-break.
Parallel computing itinerary chunks — rarely needed in interviews; sequential Hierholzer stays canonical.

Mind-Map Tags

#eulerian-trail #hierholzer #dfs-postorder #lexicographic #directed-multigraph