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

Problem (one-liner)

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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

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

Similar Problems

• 207. Course Schedule — directed graph constraints (Medium stepping stone)
• 269. Alien Dictionary — topo order on characters (Hard)
• 210. Course Schedule II — output a valid global order (Medium)

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