Skip to content

123 — Reconstruct Itinerary

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

123 — Reconstruct Itinerary

LeetCode 332 · Hard. Given a list of airline tickets represented as pairs [from, to] (three-letter airport codes), reconstruct the itinerary in order, starting from "JFK", that uses every ticket exactly once. If multiple valid itineraries exist, return the one that is smallest in lexical order when the whole route is read as a sequence of airport codes. You may assume all tickets form at least one valid itinerary.

🍽️ Intuition

Every previous graph problem in this wiki asked some version of "which nodes can I reach" — visit each airport once, mark it, move on. This problem flips that: it asks which edges you can traverse, and demands you use every single one, tickets included, exactly once, airports revisited as often as needed. That's a fundamentally different question — not "visit every city" (Hamiltonian path, famously intractable) but "use every ticket" (an Eulerian path, which is efficiently solvable precisely because it constrains edges, not nodes).

Picture the tickets as a stack of travel vouchers. You must burn every voucher, in some order, starting from JFK, and whenever you have a choice of which voucher to burn next, you're required to pick the alphabetically smallest destination. The catch: burning vouchers greedily can strand you at an airport with no more valid moves — even though every voucher could have been used, in a different order. The elegant fix (Hierholzer's algorithm) sidesteps the strand entirely by building the route back-to-front.

🚩 Pattern-Recognition Cue

"Use every edge/ticket exactly once, starting from a fixed point" is the cue for an Eulerian path, not a plain traversal. Whenever a graph problem's constraint is phrased in terms of the edges being fully consumed (rather than the nodes being fully visited), reach for Eulerian-path techniques — DFS with edges removed as they're used, backtracking on dead ends, or Hierholzer's algorithm to guarantee no backtracking is ever needed.

🐢 Brute Force

Standard DFS + backtracking: at each airport, try the lexically smallest unused ticket first; if that choice eventually leads to a dead end before all tickets are used, undo it and try the next-smallest option.

func findItineraryBruteForce(_ tickets: [[String]]) -> [String] {
    var adjacency: [String: [String]] = [:]
    for t in tickets {
        adjacency[t[0], default: []].append(t[1])
    }
    for key in adjacency.keys {
        adjacency[key]?.sort()   // try lexically smallest destination first
    }

    var route = ["JFK"]
    let totalTickets = tickets.count

    @discardableResult
    func backtrack() -> Bool {
        if route.count == totalTickets + 1 { return true }   // every ticket used
        guard let current = route.last,
              let destinations = adjacency[current], !destinations.isEmpty else {
            return false
        }
        for i in 0..<destinations.count {
            let next = destinations[i]
            adjacency[current]?.remove(at: i)   // "burn" this ticket
            route.append(next)
            if backtrack() { return true }
            route.removeLast()                  // undo: unburn the ticket
            adjacency[current]?.insert(next, at: i)
        }
        return false
    }

    backtrack()
    return route
}

// smoke test
print(findItineraryBruteForce([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]))
// ["JFK", "MUC", "LHR", "SFO", "SJC"]

Big-O: O(E!) worst case — at each of up to E tickets, the backtracking may try multiple destinations and recurse into each before finding (or failing at) a dead end. Fine for the small E ≤ 300 inputs LeetCode uses, but genuinely exponential in the worst case because failed branches get fully explored before backtracking.

🚀 Optimal

Hierholzer's algorithm: greedily walk edges, always taking the lexically smallest destination, using an explicit stack instead of recursion. When you hit a dead end (no tickets left from the current airport), that airport is finalized as the last stop of some sub-route — pop it onto the result and back up. Reversing the finalized order at the end produces the correct itinerary, with a mathematical guarantee (from Eulerian path theory) that this never requires undoing a choice.

func findItinerary(_ tickets: [[String]]) -> [String] {
    var graph: [String: [String]] = [:]
    // Sort by destination descending so removeLast() always pops the
    // lexically smallest remaining destination in O(1).
    for ticket in tickets.sorted(by: { $0[1] > $1[1] }) {
        graph[ticket[0], default: []].append(ticket[1])
    }

    var stack = ["JFK"]
    var route: [String] = []

    while let airport = stack.last {
        if graph[airport]?.isEmpty == false {
            let next = graph[airport]!.removeLast()
            stack.append(next)
        } else {
            // Dead end: this airport is finalized as a route endpoint.
            route.append(stack.removeLast())
        }
    }

    return route.reversed()
}

// smoke test
print(findItinerary([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]))
// ["JFK", "MUC", "LHR", "SFO", "SJC"]
print(findItinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]))
// ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

Big-O: O(E log E) time — dominated by the initial sort; every ticket is then pushed and popped from the stack exactly once. O(E) space for the graph, stack, and result.

🔑 The Key Insight

Both approaches greedily prefer the lexically smallest next destination — that part is identical. The difference is what happens at a dead end. The brute force treats a dead end as a signal to undo and retry a different earlier choice, which can cascade into exponential re-exploration. Hierholzer's algorithm treats a dead end as information, not failure: an airport with no tickets left is, provably, always a valid endpoint of some piece of the final route — Eulerian path theory guarantees that greedily consuming edges and recording dead ends in a stack, then reversing, reconstructs a fully valid itinerary without ever needing to backtrack. The stack isn't just a convenience for avoiding recursion — it's what lets "get stuck" become "record and back up" instead of "undo and retry."

🔗 Related Chapters

  • Graphs — tickets form a directed multigraph (repeated identical tickets are allowed and must each be used), and this problem is a full traversal defined by edges rather than nodes.
  • DFS and Backtracking — the brute force is a textbook backtracking DFS: choose the smallest option, recurse, undo on failure, try the next option.
  • Stacks — Hierholzer's algorithm is iterative DFS driven by an explicit stack; the "finalize on dead end, reverse at the end" trick is exactly what turns a stack-based traversal into a correct Eulerian path.

🧸 Memory Sentence

Reconstruct Itinerary is Eulerian path, not Hamiltonian path — burn the lexically smallest ticket every time, and when you're stuck, that's not a failure, it's the last stop of the route, recorded onto a stack and read off in reverse.

✅ Check Your Understanding

  1. Why does sorting tickets by destination descending and then calling removeLast() produce the same lexical-smallest-first order as sorting ascending and calling removeFirst() — and why is that swap worth making?
  2. Walk through why an airport can safely be "finalized" (pushed to route) the moment it has zero tickets left, even though it might be visited again earlier in the final reversed route.
  3. Construct a small ticket list where the naive greedy DFS (no backtracking, no stack trick — just always take the smallest destination and stop) fails to use every ticket. What does that failure look like, and how does Hierholzer's algorithm avoid it?

⬅️ Previous: Word Ladder · Next: Min Cost to Connect All Points ➡️

Clone this wiki locally