Reconstruct Itinerary

1. Problem & Core Objective

Given a list of airline tickets [from, to], reconstruct the itinerary in order. All tickets belong to a person who departs from "JFK", and every ticket must be used exactly once. If several valid itineraries exist, return the one with the smallest lexical order when read as a single string.

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"]    not ["JFK","SFO","ATL","JFK","ATL","SFO"]

Constraints: 1 <= tickets.length <= 300 · airports are 3 uppercase letters · a valid itinerary always exists

What's actually being tested: recognising this as an Eulerian path — use every edge exactly once, not every vertex. The greedy "always take the smallest next airport" is almost right and fails on a specific shape; Hierholzer's algorithm fixes it by building the path backwards.

2. First-Principles Thought Process

Edges, not vertices

"Use every ticket exactly once" means traverse every edge exactly once. That's an Eulerian path, not a Hamiltonian one — airports may be revisited freely, and in example 2, JFK and ATL each appear twice.

Confusing the two is the first trap: Hamiltonian path is NP-hard, Eulerian path is linear.

Why plain greedy fails

The obvious approach: from the current airport, always fly to the lexically smallest unused destination.

That gets example 2 wrong. From JFK, ATL sorts before SFO, which is right — but consider a case where the smallest choice leads into a dead end with tickets still unused. Greedy has no way back.

Concretely, with JFK→A, JFK→B, B→JFK: greedy takes A first (smaller), lands at A with no outgoing ticket, and strands JFK→B and B→JFK.

Hierholzer's insight

Walk greedily until you get stuck — no unused edges leave the current airport. That airport must be the end of the itinerary, because every other airport you can still leave has unfinished business.

So: when stuck, prepend the current airport to the result and back up. Unused edges at earlier airports get explored on the way back, and their sub-loops are inserted before the stuck portion.

void dfs(String airport) {
    while (destinations[airport] not empty)
        dfs(removeSmallest(destinations[airport]));
    route.addFirst(airport);        // post-order — after exhausting this airport
}

The addFirst after the loop is the whole algorithm. It's a post-order traversal, and the reversal is what makes dead ends land in the right place.

Why lexical order still works

Because destinations are consumed smallest-first, the greedy preference is preserved wherever it's compatible with using every edge. The post-order construction only reorders the parts where naive greedy would have failed.

3. Solution Paths

Approach 1 — Backtracking over all orderings (brute force)

public List<String> findItinerary(List<List<String>> tickets) {
    Map<String, List<String>> graph = new HashMap<>();
    for (List<String> t : tickets)
        graph.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1));
    for (List<String> dests : graph.values()) Collections.sort(dests);

    List<String> route = new ArrayList<>(List.of("JFK"));
    boolean[][] used = new boolean[tickets.size()][];      // conceptually: per-ticket flags
    return backtrack(graph, "JFK", route, tickets.size()) ? route : List.of();
}

private boolean backtrack(Map<String, List<String>> g, String at,
                          List<String> route, int remaining) {
    if (remaining == 0) return true;
    List<String> dests = g.get(at);
    if (dests == null) return false;

    for (int i = 0; i < dests.size(); i++) {
        String next = dests.remove(i);                     // take this ticket
        route.add(next);
        if (backtrack(g, next, route, remaining - 1)) return true;
        route.remove(route.size() - 1);                    // un-choose
        dests.add(i, next);
    }
    return false;
}

• Time O(E!) worst case · Space O(E)

Counter-questions on this approach

⭐ "Is this correct? And is it fast enough?"

Correct, yes — trying destinations in sorted order and returning the first complete itinerary gives the lexically smallest one, because the first success in lexicographic DFS order is the lexicographic minimum.

Fast enough, no. In the worst case it explores every permutation of tickets — O(E!). With 300 tickets that's unimaginable. It passes on small inputs and times out on the adversarial ones.

⭐ "Where does the backtracking actually happen?"

When a branch dead-ends with tickets unused. The route.remove and dests.add(i, next) undo the choice and try the next destination.

Hierholzer's insight is that this backtracking is unnecessary. A dead end isn't a failure to undo — it's information: that airport must be the itinerary's end. Recording it and continuing turns an exponential search into a linear walk.

"Why does dests.remove(i) then dests.add(i, next) work as choose/un-choose?"

It removes the ticket so it can't be reused, and reinserts it at the same index to preserve sorted order for the next attempt. Both are O(n) on an ArrayList, which adds a factor — a LinkedList or an index-based consumption avoids it.

Approach 2 — Hierholzer's algorithm (optimal)

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), k -> new PriorityQueue<>()).offer(t.get(1));

    LinkedList<String> route = new LinkedList<>();
    dfs(graph, "JFK", route);
    return route;
}

private void dfs(Map<String, PriorityQueue<String>> graph, String airport,
                 LinkedList<String> route) {
    PriorityQueue<String> dests = graph.get(airport);
    while (dests != null && !dests.isEmpty())
        dfs(graph, dests.poll(), route);                   // consume the smallest

    route.addFirst(airport);                                // POST-order — after exhausting
}

Trace — [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]:

Result [JFK, ATL, JFK, SFO, ATL, SFO] ✓

• Time O(E log E) — each edge consumed once, O(log E) per heap poll · Space O(E)

Counter-questions on this approach

⭐ "Why addFirst after the loop rather than add before it?"

Because getting stuck means the current airport is the end of the remaining itinerary — there's no unused ticket leaving it. Appending in pre-order would put it where it doesn't belong.

Adding it to the front after exhausting it means the stuck airport lands last, and everything explored afterwards from earlier airports gets prepended in front of it. The post-order plus prepend is exactly the reversal that makes dead ends land correctly.

That single line is the difference between this and naive greedy.

⭐ "Why doesn't a dead end need backtracking?"

Because a valid Eulerian path is guaranteed to exist, and in such a graph at most one vertex can be a dead end — the terminus. When the walk stops, it has found that terminus.

Any tickets still unused must hang off airports already on the path, and the recursion is still sitting on those frames. Unwinding explores them, and their loops are prepended before the terminus.

So a dead end isn't a wrong turn to undo; it's a discovery to record.

⭐ "Why does a PriorityQueue give the lexically smallest itinerary?"

poll() always removes the smallest unused destination, so at every step the greedy preference is honoured. Since a valid itinerary is guaranteed, the greedy choice never makes the problem unsolvable — it can only change where the unavoidable dead end occurs, and the post-order handles that.

Worth being precise: the greedy is safe because of the existence guarantee, not because greedy is universally correct for Eulerian paths.

"Why LinkedList rather than ArrayList?"

addFirst is O(1) on a LinkedList and O(n) on an ArrayList, which would make the whole thing O(E²). Alternatively append to an ArrayList and reverse once at the end — same result, better cache behaviour.

"What's the recursion depth?"

Up to E = 300, since each call consumes one ticket. Safe. At 10^5 edges I'd convert to an iterative version with an explicit stack.

"What if graph.get(airport) is null?"

An airport with no outgoing tickets — a legitimate terminus. The dests != null guard skips the loop and goes straight to addFirst. Without it, the terminus would throw a NullPointerException.

"Does this handle multiple identical tickets?"

Yes — PriorityQueue allows duplicates, so two JFK→ATL tickets are two separate entries and both get consumed. A Set would silently drop one.

Comparison

4. Why the Optimal Wins

Both are correct. The difference is what a dead end means.

Backtracking treats it as a failed branch to undo, which makes the search exponential. Hierholzer's recognises that in a graph with a guaranteed Eulerian path, a dead end is the terminus — so recording it and unwinding is not just valid but necessary.

That turns O(E!) into O(E log E), with the log coming only from the heap.

The framing worth keeping:

Every ticket used once is an Eulerian path — edges, not vertices. Walk greedily until stuck, then build the route backwards with addFirst on the way out. A dead end is information, not a mistake.

5. Java Prerequisites

Graph with sorted destinations

Map<String, PriorityQueue<String>> graph = new HashMap<>();
graph.computeIfAbsent(from, k -> new PriorityQueue<>()).offer(to);

PriorityQueue gives smallest-first consumption and allows duplicate tickets.

Post-order with prepend

while (dests != null && !dests.isEmpty()) dfs(dests.poll(), route);
route.addFirst(airport);        // AFTER the loop

LinkedList.addFirst is O(1); ArrayList.add(0, x) is O(n). Or append and reverse once.

Null guard on graph.get — a terminus has no outgoing edges and no map entry.

6. Interview Communication Guide

Clarifying questions: Is a valid itinerary guaranteed (yes — this is what makes the greedy safe)? Does it always start at JFK (yes)? Can the same ticket appear twice (yes — so no Set)? Can an airport be revisited (yes — it's Eulerian, not Hamiltonian)?

The pitch

"Using every ticket exactly once means traversing every edge once — that's an Eulerian path, not a Hamiltonian one. Airports can repeat; in the second example both JFK and ATL appear twice. That distinction matters because Hamiltonian path is NP-hard and Eulerian is linear.

The naive greedy — always fly to the smallest unused destination — is almost right and fails on a specific shape. With JFK→A, JFK→B, B→JFK, greedy takes A first because it's smaller, lands somewhere with no outgoing ticket, and strands the other two.

Hierholzer's algorithm fixes that. Walk greedily until you get stuck — no unused ticket leaves the current airport. Because a valid itinerary is guaranteed, that airport must be the end of the route. So instead of backtracking, I record it: addFirst to the result and unwind.

Any tickets still unused hang off airports already on the path, and the recursion is still on those frames — so unwinding explores them, and their loops get prepended in front of the stuck portion.

That post-order addFirst after the loop is the entire algorithm. A dead end is information, not a mistake to undo.

I keep each airport's destinations in a PriorityQueue so poll consumes the smallest, which gives the lexically smallest itinerary — and allows duplicate tickets, which a Set would drop.

O(E log E) — each edge consumed once, log E per poll. The backtracking version is O(E!)."

Edge cases to volunteer:

Name the third row. It's the shape where taking the lexically smaller option first leads to a dead end with tickets unused — exactly what the post-order construction repairs.

7. Follow-Up Questions — Modified Constraints

⭐ "What if no valid itinerary exists?"

The guarantee is load-bearing. Without it you'd first check the Eulerian-path conditions: the graph must be connected on its edge set, and either all vertices have equal in- and out-degree, or exactly one has out − in = 1 (the start) and one has in − out = 1 (the end). O(V + E) to verify before running.

⭐ "Return ALL valid itineraries, not just the smallest."

Back to backtracking — enumerate every Eulerian path, which is exponential. Hierholzer's produces one path, not a search space. Worth stating that the efficiency comes precisely from committing to one.

"Do it iteratively to avoid recursion."

Standard Hierholzer's uses an explicit stack: push the start, and while the stack isn't empty, either descend into an unused edge or pop and append to the route. Same O(E log E), no stack-depth limit.

"What if tickets had costs and you wanted the cheapest valid itinerary?"

Much harder — that's a travelling-salesman-flavoured problem over edges. Greedy no longer applies, because the cheapest local choice can force expensive later ones. You'd need DP over subsets or an ILP formulation.

"What if airports could be visited at most once?"

That's a Hamiltonian path, which is NP-complete. The whole tractability of this problem comes from the constraint being on edges rather than vertices — worth naming explicitly.

"What if the itinerary could start anywhere?"

Find a vertex with out − in = 1 and start there; if every vertex is balanced, the graph has an Eulerian circuit and any vertex works. The algorithm itself is unchanged.