Reconstruct Itinerary

Try every unused ticket out of the current airport in lexical order, recurse, and backtrack if a choice leads to a dead end before all tickets are used. This is correct — DFS with backtracking always eventually finds a valid Eulerian path if one exists — but it can redo enormous amounts of work: a wrong greedy pick that eventually dead-ends may not be discovered until deep into the recursion, forcing the search to backtrack out of a large subtree.

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        graph = defaultdict(list)
        for src, dst in tickets:
            graph[src].append(dst)
        for city in graph:
            graph[city].sort()

        n = len(tickets)
        used = [False] * n
        path = ["JFK"]

        def backtrack(city: str) -> bool:
            if len(path) == n + 1:
                return True
            for i, (src, dst) in enumerate(tickets):
                if not used[i] and src == city:
                    used[i] = True
                    path.append(dst)
                    if backtrack(dst):
                        return True
                    path.pop()
                    used[i] = False
            return False

        backtrack("JFK")
        return path

In the worst case (a dense graph with many dead-end traps) this degenerates toward trying permutations of edges, i.e. O(E!). It passes on LeetCode’s test data because the graphs are small and forgiving, but it is not the intended solution.

The key insight fixing the brute force’s blind spot: never backtrack on a used edge — instead, record airports in postorder as you get stuck, and reverse at the end. This is Hierholzer’s algorithm for Eulerian paths. Concretely:

1. Build an adjacency list, sorting each airport’s destinations lexically so the smallest option is tried first. Use a structure that lets you pop the smallest destination in O(log d) — a min-heap per node — or, equivalently, sort descending and pop() from the end.
2. DFS from "JFK", consuming (popping) an edge each time you traverse it.
3. When a node runs out of unused outgoing edges, append it to the result list and return up the call stack — this is the “dead end” that Hierholzer’s algorithm relies on being correct, not a mistake to recover from.
4. Reverse the result at the end.

Why appending on dead-end and reversing works: every airport with equal in-degree and out-degree will always have an unused edge to leave through until the very last visit, so the recursion only “gets stuck” for good at nodes that are the true end of the walk. Any leftover sub-cycles found while stuck get spliced into the postorder naturally because the DFS resumes them before finishing the outer call.

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        graph = defaultdict(list)
        # Sort tickets reverse-lexically so pop() (from the end) yields
        # the lexically smallest destination first — O(1) per pop.
        for src, dst in sorted(tickets, reverse=True):
            graph[src].append(dst)

        route = []

        def dfs(airport: str) -> None:
            while graph[airport]:
                nxt = graph[airport].pop()
                dfs(nxt)
            route.append(airport)

        dfs("JFK")
        return route[::-1]

Worked example — tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]. Adjacency (sorted): JFK → [ATL, SFO], SFO → [ATL], ATL → [JFK, SFO].

Watch three things in this trace: how every pop grows the DFS call stack and every append shrinks it; how the emerald route collects airports in postorder, from the end of the journey backward; and the final step that reverses that route into the answer.

Reversing gives ["JFK","ATL","JFK","SFO","ATL","SFO"], matching the expected output — the same chain the call stack spelled out at its deepest point.

Complexity: sorting the tickets costs O(E log E); the DFS itself visits each edge exactly once (O(E)), popping from the end of a sorted list in O(1) — so the whole algorithm is O(E log E) time, dominated by the sort. Space is O(V + E) for the adjacency list, recursion stack, and result.