332. Reconstruct Itinerary (Hard)

Problem

You are given a list of airline tickets where tickets[i] = [fromᵢ, toᵢ]. Reconstruct the itinerary in order. All tickets belong to one person who departs from "JFK". You must use every ticket exactly once; if multiple valid itineraries exist, return the lexicographically smallest.

Example

tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] → ["JFK","MUC","LHR","SFO","SJC"]
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] → ["JFK","ATL","JFK","SFO","ATL","SFO"]

LeetCode 332 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, backtracking

Try every permutation of tickets starting from JFK; pick the lexicographically smallest valid one.

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets):                  # L1: O(E log E) sort
        graph[src].append(dst)                        # L2: O(1) amortized per append

    target_len = len(tickets) + 1                     # L3: O(1)

    def dfs(node, path):
        if len(path) == target_len:                   # L4: O(1) base case check
            return list(path)
        for i, nb in enumerate(graph[node]):          # L5: iterate over neighbors
            if nb is None:
                continue
            graph[node][i] = None                     # L6: O(1) mark used
            path.append(nb)                           # L7: O(1) amortized
            result = dfs(nb, path)                    # L8: recurse
            if result:
                return result
            path.pop()                                # L9: O(1) backtrack
            graph[node][i] = nb                       # L10: O(1) restore
        return None

    return dfs("JFK", ["JFK"])

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, (string | null)[]>();
    const sorted = [...tickets].sort((a, b) =>
        a[0] !== b[0] ? a[0].localeCompare(b[0]) : a[1].localeCompare(b[1])
    );
    for (const [src, dst] of sorted) {               // L1: O(E log E) sort
        if (!graph.has(src)) graph.set(src, []);
        graph.get(src)!.push(dst);                   // L2: O(1) amortized per append
    }

    const targetLen = tickets.length + 1;            // L3: O(1)

    function dfs(node: string, path: string[]): string[] | null {
        if (path.length === targetLen) return [...path]; // L4: O(1) base case check
        const neighbors = graph.get(node) ?? [];
        for (let i = 0; i < neighbors.length; i++) { // L5: iterate over neighbors
            const nb = neighbors[i];
            if (nb === null) continue;
            neighbors[i] = null;                     // L6: O(1) mark used
            path.push(nb);                           // L7: O(1) amortized
            const result = dfs(nb, path);            // L8: recurse
            if (result) return result;
            path.pop();                              // L9: O(1) backtrack
            neighbors[i] = nb;                       // L10: O(1) restore
        }
        return null;
    }

    return dfs('JFK', ['JFK']) ?? [];
}

func findItinerary(tickets [][]string) []string {
    graph := make(map[string][]*string)
    sorted := make([][]string, len(tickets))
    copy(sorted, tickets)
    sort.Slice(sorted, func(i, j int) bool {           // L1: O(E log E) sort
        if sorted[i][0] != sorted[j][0] { return sorted[i][0] < sorted[j][0] }
        return sorted[i][1] < sorted[j][1]
    })
    for _, t := range sorted {                         // L2: O(1) amortized per append
        dst := t[1]
        graph[t[0]] = append(graph[t[0]], &dst)
    }
    targetLen := len(tickets) + 1                      // L3: O(1)
    var result []string
    var dfs func(node string, path []string) bool
    dfs = func(node string, path []string) bool {
        if len(path) == targetLen { result = append([]string{}, path...); return true } // L4
        for i, nb := range graph[node] {               // L5: iterate over neighbors
            if nb == nil { continue }
            graph[node][i] = nil                       // L6: O(1) mark used
            path = append(path, *nb)                   // L7: O(1) amortized
            if dfs(*nb, path) { return true }          // L8: recurse
            path = path[:len(path)-1]                  // L9: O(1) backtrack
            graph[node][i] = nb                        // L10: O(1) restore
        }
        return false
    }
    dfs("JFK", []string{"JFK"})
    return result
}

final class Solution {
    func findItinerary(_ tickets: [[String]]) -> [String] {
        let ordered = tickets.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] }; var used = Array(repeating: false, count: ordered.count), route = ["JFK"]
        func search() -> Bool { if route.count == ordered.count + 1 { return true }; let airport = route.last!; for index in ordered.indices where !used[index] && ordered[index][0] == airport { used[index] = true; route.append(ordered[index][1]); if search() { return true }; route.removeLast(); used[index] = false }; return false }
        _ = search(); return route
    }
}

Where the time goes, line by line

Variables: V = number of unique airports, E = len(tickets).

Line	Per-call cost	Times executed	Contribution
L1 (sort tickets)	$O(E log E)$	1	$O(E log E)$
L2 (build graph)	$O(1)$	E	$O(E)$
L5/L8 (backtrack DFS)	$O(E)$	up to E^E	$O(E^E)$ ← dominates
L6/L10 (mark/restore)	$O(1)$	per call	$O(E^E)$

At each step, up to E tickets could be chosen; with E steps total, the search tree has up to E^E leaves. In practice, lexicographic sorting prunes this heavily, but the worst case is still exponential.

Complexity

Time: $O(E^E)$ worst case, driven by L5/L8 (unconstrained backtracking over all permutations).
Space: $O(E)$ for the recursion stack and path.

Approach 2: Hierholzer’s algorithm with lexicographic neighbor selection (optimal)

Hierholzer’s builds an Eulerian path in $O(E)$ . The trick: always recurse into the lexicographically smallest outgoing edge, then prepend the current node to the result as the recursion unwinds.

from collections import defaultdict
import heapq

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(graph[src], dst)               # L1: O(log E) per push; total O(E log E)

    itinerary = []
    def dfs(node):
        while graph[node]:                            # L2: loop until no more edges from this node
            nb = heapq.heappop(graph[node])           # L3: O(log E) pop smallest neighbor
            dfs(nb)                                   # L4: recurse; each edge visited exactly once
        itinerary.append(node)                        # L5: O(1), post-order append

    dfs("JFK")
    return itinerary[::-1]                            # L6: O(E) reverse to get forward path

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, MinHeap>();
    for (const [src, dst] of tickets) {
        if (!graph.has(src)) graph.set(src, new MinHeap());
        graph.get(src)!.push(dst);                   // L1: O(log E) per push; total O(E log E)
    }

    const itinerary: string[] = [];
    function dfs(node: string): void {
        const heap = graph.get(node);
        while (heap && heap.size > 0) {              // L2: loop until no more edges from this node
            const nb = heap.pop();                   // L3: O(log E) pop smallest neighbor
            dfs(nb);                                 // L4: recurse; each edge visited exactly once
        }
        itinerary.push(node);                        // L5: O(1), post-order append
    }

    dfs('JFK');
    return itinerary.reverse();                      // L6: O(E) reverse to get forward path
}

// See 332-reconstruct-itinerary-approach2.go for the full runnable program.
// Core function uses container/heap StringHeap for lexicographic neighbor selection.
func findItinerary(tickets [][]string) []string {
    graph := make(map[string]*StringHeap)
    for _, t := range tickets {
        src, dst := t[0], t[1]
        if graph[src] == nil { graph[src] = &StringHeap{}; heap.Init(graph[src]) }
        heap.Push(graph[src], dst)                   // L1: O(log E) per push; total O(E log E)
    }
    var itinerary []string
    var dfs func(node string)
    dfs = func(node string) {
        for graph[node] != nil && graph[node].Len() > 0 {  // L2: loop until no more edges
            nb := heap.Pop(graph[node]).(string)     // L3: O(log E) pop smallest neighbor
            dfs(nb)                                  // L4: recurse; each edge once
        }
        itinerary = append(itinerary, node)          // L5: O(1), post-order append
    }
    dfs("JFK")
    // reverse                                       // L6: O(E)
    for i, j := 0, len(itinerary)-1; i < j; i, j = i+1, j-1 {
        itinerary[i], itinerary[j] = itinerary[j], itinerary[i]
    }
    return itinerary
}

Where the time goes, line by line

Variables: V = number of unique airports, E = len(tickets).

Line	Per-call cost	Times executed	Contribution
L1 (build heaps)	$O(log E)$	E	$O(E log E)$
L2 (while loop)	$O(1)$	E total across all calls	$O(E)$
L3 (heappop)	$O(log E)$	E	$O(E log E)$ ← dominates
L4 (recurse)	$O(1)$ overhead	E (one per edge)	$O(E)$
L5 (append)	$O(1)$	V + E	$O(E)$
L6 (reverse)	$O(E)$	1	$O(E)$

Each ticket is a directed edge used exactly once, so the total number of heappop calls equals E. Each pop costs $O(log E)$ . Every other operation is $O(E)$ total. The heap overhead from building at L1 is also $O(E log E)$ .

Complexity

Time: $O(E log E)$ , driven by L1/L3 (heap construction and per-edge pops).
Space: $O(E)$ for the heap entries plus the recursion stack (depth up to E in degenerate cases).

Why it works

In an Eulerian path, you may hit dead ends along the way. Hierholzer’s handles this by building the path in reverse: when you can’t move forward, the current node is part of the end of the final path. Appending in post-order then reversing gives the full traversal.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findItinerary(_ tickets: [[String]]) -> [String] {
        var graph: [String: [String]] = [:]
        for ticket in tickets { graph[ticket[0], default: []].append(ticket[1]) }
        for airport in graph.keys { graph[airport]!.sort(by: >) }
        var route: [String] = []
        func visit(_ airport: String) { while let next = graph[airport]?.popLast() { visit(next) }; route.append(airport) }
        visit("JFK"); return route.reversed()
    }
}

Approach 3: Hierholzer’s with sorted adjacency lists + pointer

Same idea; sort adjacency lists once and iterate with a pointer instead of repeatedly popping from a heap.

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)                        # L1: O(E log E) for sort; O(1) per append

    itinerary = []
    stack = ["JFK"]                                   # L2: O(1), explicit stack replaces recursion
    while stack:                                      # L3: outer loop, runs E+1 times total
        while graph[stack[-1]]:                       # L4: inner loop, pops one edge per iteration
            stack.append(graph[stack[-1]].pop())      # L5: O(1) list pop from end + stack push
        itinerary.append(stack.pop())                 # L6: O(1), node has no more outgoing edges
    return itinerary[::-1]                            # L7: O(E) reverse

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, string[]>();
    // sort descending so pop() from end gives lexicographically smallest
    const sorted = [...tickets].sort((a, b) => {
        const cmpSrc = b[0].localeCompare(a[0]);
        return cmpSrc !== 0 ? cmpSrc : b[1].localeCompare(a[1]);
    });
    for (const [src, dst] of sorted) {               // L1: O(E log E) for sort; O(1) per append
        if (!graph.has(src)) graph.set(src, []);
        graph.get(src)!.push(dst);
    }

    const itinerary: string[] = [];
    const stack: string[] = ['JFK'];                  // L2: O(1), explicit stack replaces recursion
    while (stack.length > 0) {                       // L3: outer loop, runs E+1 times total
        const top = stack[stack.length - 1];
        const neighbors = graph.get(top);
        if (neighbors && neighbors.length > 0) {
            stack.push(neighbors.pop()!);             // L5: O(1) list pop from end + stack push
        } else {
            itinerary.push(stack.pop()!);             // L6: O(1), node has no more outgoing edges
        }
    }
    return itinerary.reverse();                       // L7: O(E) reverse
}

// See 332-reconstruct-itinerary-approach3.go for the full runnable program.
// Core function: sort descending, pop from end = lexicographically smallest.
func findItinerary(tickets [][]string) []string {
    graph := make(map[string][]string)
    sort.Slice(tickets, func(i, j int) bool {          // L1: O(E log E) for sort
        if tickets[i][0] != tickets[j][0] { return tickets[i][0] > tickets[j][0] }
        return tickets[i][1] > tickets[j][1]
    })
    for _, t := range tickets { graph[t[0]] = append(graph[t[0]], t[1]) }
    var itinerary []string
    stack := []string{"JFK"}                           // L2: O(1), explicit stack
    for len(stack) > 0 {                               // L3: outer loop, runs E+1 times total
        top := stack[len(stack)-1]
        if nb := graph[top]; len(nb) > 0 {
            stack = append(stack, nb[len(nb)-1])       // L5: O(1) list pop from end + stack push
            graph[top] = nb[:len(nb)-1]
        } else {
            itinerary = append(itinerary, stack[len(stack)-1])  // L6: O(1)
            stack = stack[:len(stack)-1]
        }
    }
    for i, j := 0, len(itinerary)-1; i < j; i, j = i+1, j-1 {
        itinerary[i], itinerary[j] = itinerary[j], itinerary[i]  // L7: O(E) reverse
    }
    return itinerary
}

Where the time goes, line by line

Variables: V = number of unique airports, E = len(tickets).

Line	Per-call cost	Times executed	Contribution
L1 (sort + build)	$O(E log E)$	1	$O(E log E)$ ← dominates
L3 (outer loop)	$O(1)$	E+V	$O(E)$
L4/L5 (inner pop+push)	$O(1)$	E	$O(E)$
L6 (append to result)	$O(1)$	E+1	$O(E)$
L7 (reverse)	$O(E)$	1	$O(E)$

Sorting once at L1 is the only super-linear step. Everything after is amortized $O(1)$ per edge because each edge is pushed and popped exactly once from both graph[...] and stack.

Complexity

Time: $O(E log E)$ for the sort at L1; all subsequent operations are $O(E)$ .
Space: $O(E)$ for the adjacency lists and stack.

Iterative form avoids recursion depth concerns.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findItinerary(_ tickets: [[String]]) -> [String] {
        var graph: [String: [String]] = [:]
        for ticket in tickets { graph[ticket[0], default: []].append(ticket[1]) }
        for airport in graph.keys { graph[airport]!.sort() }
        var nextIndex: [String: Int] = [:]
        var route: [String] = []
        func visit(_ airport: String) {
            let neighbors = graph[airport] ?? []
            while nextIndex[airport, default: 0] < neighbors.count {
                let index = nextIndex[airport, default: 0]
                nextIndex[airport] = index + 1
                visit(neighbors[index])
            }
            route.append(airport)
        }
        visit("JFK"); return route.reversed()
    }
}

Summary

Approach	Time	Space
Brute-force backtracking	$O(E^E)$	$O(E)$
Hierholzer’s + heap	$O(E log E)$	$O(E)$
Hierholzer’s iterative + sort	$O(E log E)$	$O(E)$

Hierholzer’s is the canonical answer. The “build in reverse” trick is subtle; recognizing it is the whole problem.

Test cases

# Quick smoke tests, paste into a REPL or save as test_332.py and run.
# Uses the canonical implementation (Hierholzer's iterative, Approach 3).

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)
    itinerary = []
    stack = ["JFK"]
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop())
        itinerary.append(stack.pop())
    return itinerary[::-1]

def _run_tests():
    # Example 1 from problem statement
    assert find_itinerary([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]) == ["JFK","MUC","LHR","SFO","SJC"]
    # Example 2: multiple valid itineraries, pick lexicographically smallest
    assert find_itinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]) == ["JFK","ATL","JFK","SFO","ATL","SFO"]
    # Single ticket
    assert find_itinerary([["JFK","ATL"]]) == ["JFK","ATL"]
    # Linear chain
    assert find_itinerary([["JFK","A"],["A","B"],["B","C"]]) == ["JFK","A","B","C"]
    # Loop back to start
    assert find_itinerary([["JFK","ATL"],["ATL","JFK"]]) == ["JFK","ATL","JFK"]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function findItinerary(tickets: string[][]): string[] {
    const graph = new Map<string, string[]>();
    const sorted = [...tickets].sort((a, b) => {
        const cmpSrc = b[0].localeCompare(a[0]);
        return cmpSrc !== 0 ? cmpSrc : b[1].localeCompare(a[1]);
    });
    for (const [src, dst] of sorted) {
        if (!graph.has(src)) graph.set(src, []);
        graph.get(src)!.push(dst);
    }
    const itinerary: string[] = [];
    const stack: string[] = ['JFK'];
    while (stack.length > 0) {
        const top = stack[stack.length - 1];
        const neighbors = graph.get(top);
        if (neighbors && neighbors.length > 0) {
            stack.push(neighbors.pop()!);
        } else {
            itinerary.push(stack.pop()!);
        }
    }
    return itinerary.reverse();
}

console.assert(JSON.stringify(findItinerary([['MUC','LHR'],['JFK','MUC'],['SFO','SJC'],['LHR','SFO']])) === JSON.stringify(['JFK','MUC','LHR','SFO','SJC']));
console.assert(JSON.stringify(findItinerary([['JFK','SFO'],['JFK','ATL'],['SFO','ATL'],['ATL','JFK'],['ATL','SFO']])) === JSON.stringify(['JFK','ATL','JFK','SFO','ATL','SFO']));
console.assert(JSON.stringify(findItinerary([['JFK','ATL']])) === JSON.stringify(['JFK','ATL']));
console.assert(JSON.stringify(findItinerary([['JFK','A'],['A','B'],['B','C']])) === JSON.stringify(['JFK','A','B','C']));
console.assert(JSON.stringify(findItinerary([['JFK','ATL'],['ATL','JFK']])) === JSON.stringify(['JFK','ATL','JFK']));
console.log("all tests pass");

Graphs, Eulerian path; Hierholzer’s algorithm
Heaps / Priority Queues, lexicographic neighbor selection

Permutations, the ordered arrangement pattern where position and used items define the search.
DFS, the depth first traversal habit of following one branch before returning.

332. Reconstruct Itinerary (Hard)

Problem

Try it yourself

Approach 1: Brute force, backtracking

Approach 2: Hierholzer’s algorithm with lexicographic neighbor selection (optimal)

Why it works

Approach 3: Hierholzer’s with sorted adjacency lists + pointer

Summary

Test cases

Related data structures

Related concepts