Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
LeetCode 332

Reconstruct Flight Path

HardJul 26, 2026graphdfseulerian-pathhierholzer's-algorithm

`courseScheduleII`'s footnote comes due: Kahn's algorithm got a topological order for free because its dequeue order already respected dependencies, and BFS-by-inDegree was noted as the version that didn't need a post-order reversed. This is that other case — a stack-based DFS that records each airport on the way *out*, once it's out of tickets, so the raw order comes out backwards and `reverse()` is the last step, not cleanup.

The problem

Implement `findItinerary(tickets)` where `tickets[i] = [from, to]` is a directed edge and every ticket must be used exactly once, starting from `"JFK"`. Return the itinerary as an array of airport codes; if more than one valid itinerary uses every ticket, return the lexicographically smallest one.

`tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]` returns `["JFK","HOU","JFK","SEA","JFK"]` over the equally-valid `["JFK","SEA","JFK","HOU","JFK"]` — both spend every ticket, but `HOU` sorts before `SEA`, so leaving `JFK` for `HOU` first wins.

The approach

Same adjacency-list build as every earlier edge-list entry — `graph[from].push(to)` — with one difference: an airport can legitimately appear as `from` more than once, since `tickets` is a multiset of tickets, not a set of unique edges. Each destination has to be *consumed* once used, not just visited like every earlier `graph[node]` walk in this log.

Every destination list is sorted ascending, then reversed, so `graph[node].pop()` always removes the current lexicographically smallest unused destination off the end in `O(1)` — the same 'sort once, read from an end' idea as `networkDelayTime`, but a single upfront sort instead of a resort per pop, since consuming an already-sorted list in order never changes what's left.

The traversal is Hierholzer's algorithm, run with an explicit stack seeded at `"JFK"`: each iteration either pushes the next unused ticket out of the node on top (going deeper while tickets remain) or, once that node is out of tickets, pops it straight into `route`. A node only lands in `route` once every ticket leaving it has been spent, so the airport that runs out first is recorded first — `"JFK"` runs out last, since it's only stuck once every branch reachable from it has been fully drained back to it, so it ends up last in `route`.

`route.reverse()` is what turns that 'stuck-first, stuck-last' order back into 'departed-first, departed-last' — `"JFK"`, last into `route`, becomes first out, exactly where the itinerary actually starts.

The solution

js
class Solution {
    /**
     * @param {string[][]} tickets
     * @return {string[]}
     */
    findItinerary(tickets) {
        const graph = {};
        for (const [from, to] of tickets) {
            if (!(from in graph)) graph[from] = [];
            graph[from].push(to);
        }
        for (const from in graph) {
            graph[from].sort().reverse();
        }

        const stack = ["JFK"];
        const route = [];

        while (stack.length) {
            const node = stack[stack.length - 1];
            if (graph[node] && graph[node].length) {
                stack.push(graph[node].pop());
            } else {
                route.push(stack.pop());
            }
        }

        return route.reverse();
    }
}

Time O(E log E)Space O(V + E)

All entries