Reconstruct Itinerary

HardGraphs · Eulerian Path (Hierholzer) · Heap🧩 MST & Euler Paths LeetCode #332 ↗Updated Oct 30, 2026

Problem

You are given a pile of one-way flight tickets, each [from, to]. The traveller starts at "JFK" and must use every ticket exactly once. Rebuild the trip as a list of airports. If several trips are possible, return the one that is lexicographically smallest when read as a sequence of airport codes. At least one valid trip is guaranteed.

Input[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]Output["JFK","MUC","LHR","SFO","SJC"]

Input[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]Output["JFK","ATL","JFK","SFO","ATL","SFO"]

Input[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]Output["JFK","NRT","JFK","KUL"]

1 ≤ tickets.length ≤ 300 · codes are 3 uppercase letters · from ≠ to · a valid itinerary always exists

Try it yourself

Java

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Using every ticket once is an Eulerian path. Hierholzer's algorithm always takes the smallest remaining destination and appends an airport only when it is a dead end; dead ends are exactly the parts that must come last, so the reversed finishing order is the answer.

PatternMST & Euler Paths

Instinct "Connect every point for the least total cost" means a minimum spanning tree; "use every edge or ticket exactly once" means an Euler path.

Memory hack MST - grab the cheapest bridge that joins two separate islands. Euler - wander until stuck, write the stop down on the way back, then reverse.

Open the MST & Euler Paths guide →

Approaches

Brute ForceBacktracking in Lexical Order

Time Exponential worst caseSpace O(E)

Sort each airport's destinations. From JFK, try unused tickets in alphabetical order, recursing; if a branch gets stuck before all tickets are used, undo it and try the next. Because choices are tried smallest-first, the first complete trip found is the lexicographically smallest.

Java

private Map<String, List<String>> adj = new HashMap<>();
private Map<String, boolean[]> used = new HashMap<>();
private List<String> path = new ArrayList<>();

public List<String> findItinerary(List<List<String>> tickets) {
    for (List<String> t : tickets) {
        adj.computeIfAbsent(t.get(0), x -> new ArrayList<>()).add(t.get(1));
    }
    for (Map.Entry<String, List<String>> e : adj.entrySet()) {
        Collections.sort(e.getValue());
        used.put(e.getKey(), new boolean[e.getValue().size()]);
    }
    path.add("JFK");
    dfs("JFK", tickets.size());
    return path;
}

private boolean dfs(String at, int remaining) {
    if (remaining == 0) return true;
    List<String> dests = adj.get(at);
    if (dests == null) return false;
    boolean[] u = used.get(at);
    for (int i = 0; i < dests.size(); i++) {
        if (u[i]) continue;
        // An identical unused ticket just before i already failed
        if (i > 0 && !u[i - 1] && dests.get(i).equals(dests.get(i - 1))) continue;
        u[i] = true;
        path.add(dests.get(i));
        if (dfs(dests.get(i), remaining - 1)) return true;
        path.remove(path.size() - 1);
        u[i] = false;
    }
    return false;
}

Correct and intuitive, but a dead-end-heavy graph can force heavy backtracking.

OptimalHierholzer's Algorithm with Min-Heaps

Time O(E log E)Space O(E)

Store each airport's destinations in a min-heap. Walk with a stack: while the top airport still has tickets, fly to its smallest destination; once it has none, pop it onto the front of the route. Every ticket is consumed once and no choice is ever undone.

Java

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    for (List<String> t : tickets) {
        graph.computeIfAbsent(t.get(0), x -> new PriorityQueue<>()).add(t.get(1));
    }
    LinkedList<String> route = new LinkedList<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push("JFK");
    while (!stack.isEmpty()) {
        PriorityQueue<String> next = graph.get(stack.peek());
        if (next != null && !next.isEmpty()) {
            stack.push(next.poll()); // take the smallest remaining ticket
        } else {
            route.addFirst(stack.pop()); // dead end: it belongs at the back
        }
    }
    return route;
}

Linear apart from heap operations; never backtracks.

Pro tip

Trace JFK→KUL, JFK→NRT→JFK: greedy goes to KUL first and gets stuck — Hierholzer simply places KUL last.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking in Lexical Order	`Exponential worst case`	`O(E)`
Optimal	Hierholzer's Algorithm with Min-Heaps	`O(E log E)`	`O(E)`

Common pitfalls

Pure greedy “always fly to the smallest” without post-order — can strand unused tickets.
Using a Set for destinations — duplicate tickets between the same airports are allowed.
Appending to the end instead of the front (or forgetting to reverse) in Hierholzer.

Interview tips

Name it as an Eulerian path problem right away; the start node is fixed at JFK.
Walk through a dead-end example to show why post-order fixes greedy.
Mention the backtracking solution first, then explain why Hierholzer never needs to undo.

Pattern

Eulerian path (Hierholzer) → use every edge exactly once; emit nodes in post-order and reverse.

My notes saved in this browser