Reconstruct Itinerary

Problem

You hold a pile of plane tickets, each tickets[i] = [from, to] — 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 separately).

If more than one complete itinerary exists, return the one that is smallest in lexical order when the airport codes are read off 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 chain into a single line.
• tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] → ["JFK","ATL","JFK","SFO","ATL","SFO"] — ["JFK","SFO",...] also uses all tickets, but starting with ATL is lexically smaller.
• tickets = [["JFK","AAA"],["AAA","JFK"],["JFK","BBB"]] → ["JFK","AAA","JFK","BBB"] — greedily flying to AAA first still works because the return ticket brings you back.

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; 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

class Solution:
    def findItinerary(self, 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 — a failed branch can re-enumerate orderings of the remaining tickets. It passes on LeetCode’s small inputs (E ≤ 300) but degenerates on adversarial graphs with many interchangeable loops; it’s also simply the wrong tool, because Eulerian paths never need search.

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

The insight: an Eulerian path (a walk using every edge exactly once — here guaranteed to exist) can be built with zero backtracking. Hierholzer’s algorithm: 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. Write it down, step back, and continue consuming edges; every airport gets written after all its remaining edges are used up. Reversing that 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

class Solution:
    def findItinerary(self, 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"]]):

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

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

Why the dead-end case works too ([["JFK","AAA"],["AAA","JFK"],["JFK","BBB"]]): greedy walk JFK → AAA → JFK → BBB gets stuck at BBB — 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: O(E log E) time, 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 duplicate tickets are distinct edges — a set-based adjacency silently merges them; use a list/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, never backtracking search. The general principle: a vertex can be finalized only when all its edges are exhausted, so build the answer back-to-front. Contrast with “visit every vertex once” (Hamiltonian — exponential) and with shortest-path questions (Dijkstra/BFS): identifying which classic the problem secretly is, is most of the work in Advanced Graphs.