Reconstruct Itinerary

Problem

You are given a list of airline tickets where each tickets[i] = [from, to] is a one-way flight between two three-letter airport codes. Starting from "JFK", build an itinerary that uses every ticket exactly once. Duplicate tickets count as separate flights.

If more than one complete itinerary exists, return the one that is smallest in lexical order when the airport codes are read as a single sequence. You may assume at least one valid itinerary exists.

In graph terms, tickets are directed edges, and you must find a path from "JFK" that traverses every edge exactly once (an Eulerian path), breaking ties alphabetically.

Examples

• tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] → ["JFK","MUC","LHR","SFO","SJC"] — the tickets form a single chain.
• tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] → ["JFK","ATL","JFK","SFO","ATL","SFO"] — starting ["JFK","SFO",...] also uses all tickets, but starting with ATL is lexically smaller.
• tickets = [["JFK","AAA"],["AAA","JFK"],["JFK","BBB"]] → ["JFK","AAA","JFK","BBB"] — flying to AAA first is valid because the return ticket brings you back to JFK.

Constraints

• 1 <= len(tickets) <= 300
• Airport codes are exactly 3 uppercase letters; every itinerary starts at "JFK".
• At least one valid itinerary exists.

Think about it first

TL;DR

Eulerian path via Hierholzer’s algorithm with min-heap adjacency — O(E log E) time, O(E) space.

Approach 1 — Brute force (backtracking in alphabetical order)

Sort tickets so each airport’s destinations are tried alphabetically, then DFS using one unused ticket at a time. On a dead end before all tickets are used, un-use the ticket and try the next destination. The first complete itinerary found is the lexically smallest, because choices are explored in sorted order.

from collections import defaultdict

def findItinerary(tickets: list[list[str]]) -> list[str]:
    adj = defaultdict(list)
    for src, dst in sorted(tickets):
        adj[src].append(dst)

    n = len(tickets)
    route = ["JFK"]

    def backtrack(city: str) -> bool:
        if len(route) == n + 1:
            return True
        dests = adj[city]
        for i, nxt in enumerate(dests):
            if nxt is None:
                continue
            if i > 0 and dests[i - 1] == nxt:
                continue  # identical ticket just failed; skip duplicate
            dests[i] = None
            route.append(nxt)
            if backtrack(nxt):
                return True
            route.pop()
            dests[i] = nxt
        return False

    backtrack("JFK")
    return route

Complexity: worst case exponential, because a failed branch can re-enumerate orderings of the remaining tickets. It passes LeetCode’s small inputs (E ≤ 300) but degenerates on adversarial graphs with many interchangeable loops. It is also the wrong tool: Eulerian paths never require search.

Approach 2 — Hierholzer’s algorithm (greedy + reverse postorder)

An Eulerian path (a walk using every edge exactly once, guaranteed to exist here) can be built with no backtracking. Walk greedily until you get stuck. Getting stuck means the current airport has no unused departures, so it must be the itinerary’s last stop. Record it, step back, and continue consuming edges. Every airport is recorded only after all its remaining edges are used, so reversing the log yields the itinerary. Taking the alphabetically smallest departure first (a min-heap per airport) makes the result lexically smallest.

from collections import defaultdict
import heapq

def findItinerary(tickets: list[list[str]]) -> list[str]:
    adj = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(adj[src], dst)

    route = []
    stack = ["JFK"]
    while stack:
        # fly greedily until stuck at stack[-1]
        while adj[stack[-1]]:
            nxt = heapq.heappop(adj[stack[-1]])
            stack.append(nxt)
        # stuck: this airport is finished; emit it
        route.append(stack.pop())
    route.reverse()
    return route

Walkthrough (tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]):

The tickets form this directed graph:

flowchart LR
    JFK --> SFO
    JFK --> ATL
    SFO --> ATL
    ATL --> JFK
    ATL --> SFO

Heaps: JFK: [ATL, SFO], ATL: [JFK, SFO], SFO: [ATL].

1. Greedy walk, always popping the smallest destination: JFK → ATL → JFK → SFO → ATL → SFO. The stack holds those six airports, and SFO has no departures left.
2. Stuck at SFO, so emit it: route = [SFO]. Back at ATL: both of its tickets (ATL→JFK and ATL→SFO) were consumed during the walk, so its heap is empty. Stuck, emit: route = [SFO, ATL].
3. SFO, JFK, ATL, JFK all have empty heaps now, so they pop off in turn: route = [SFO, ATL, SFO, JFK, ATL, JFK].
4. Reverse to ["JFK","ATL","JFK","SFO","ATL","SFO"], which matches the expected answer. The naive greedy JFK→SFO start never happened because ATL sorts first.

The dead-end case works the same way ([["JFK","AAA"],["AAA","JFK"],["JFK","BBB"]]): the greedy walk JFK → AAA → JFK → BBB gets stuck at BBB, which is emitted last, exactly where the dead end belongs. No backtracking was needed even though BBB is a trap under plain greedy-with-restart.

Complexity: each ticket is pushed and popped from a heap once, giving O(E log E) time and O(E) space. A recursive DFS version with pre-sorted lists popped from the back is the same idea: recurse on the smallest destination, append the airport on unwind, reverse at the end.

Common pitfalls

• Treating it as “visit every airport once” (Hamiltonian, NP-hard) instead of “use every ticket once” (Eulerian, linear). Airports may and do repeat.
• Plain greedy without the postorder trick: always flying to the smallest destination and never recording-on-stuck strands you in dead ends like the BBB example.
• Forgetting that duplicate tickets are distinct edges. A set-based adjacency silently merges them; use a list or heap (multiset).
• Emitting airports in walk order instead of reverse postorder. The output must be built from the stuck end backwards.

Pattern takeaway

“Use every edge exactly once” is the Eulerian-path signature: reach for Hierholzer’s postorder walk, not backtracking search. The general principle is that a vertex can be finalized only when all its edges are exhausted, so build the answer back-to-front. Contrast this with “visit every vertex once” (Hamiltonian, exponential) and with shortest-path questions (Dijkstra/BFS). Identifying which classic problem you are looking at is most of the work in Advanced Graphs.