Reconstruct Itinerary

LeetCode 332: Reconstruct Itinerary Solution & Explanation

Problem Overview

TL;DR: Build a destination min-heap for every airport, recursively consume the smallest available ticket, append airports after exhausting their outgoing tickets, then reverse the recorded route to obtain the lexicographically smallest valid itinerary.

In LeetCode 332: Reconstruct Itinerary, each ticket represents one directed flight and must be used exactly once. The itinerary must begin at "JFK", and when several complete itineraries are possible, the full airport sequence must be lexicographically smallest.

Tickets can contain duplicate flights, so each ticket must be treated as an independent edge. This is a popular interview question because it combines graph traversal, ordered choices, edge consumption, and backtracking-style stack behavior. The LeetCode 332 Solution below uses the required Stack Patterns approach with a Simulation / Backtracking Helper subpattern.

Brute Force Approach for Reconstruct Itinerary

A direct solution is to try every currently available ticket from the current airport:

1. Start at "JFK".
2. Find every unused ticket departing from the current airport.
3. Try those tickets in lexicographical order.
4. Mark one ticket as used and continue recursively.
5. If all tickets are used, record the itinerary.
6. If a branch cannot use every ticket, undo the choice and try another ticket.
7. Return the lexicographically smallest complete itinerary.

A naive version can be expressed as:

backtrack(currentAirport, usedTickets, route):
    if route contains tickets + 1 airports:
        save route
        return

    for each ticket departing from currentAirport:
        if ticket is unused:
            mark ticket as used
            append ticket.destination to route

            backtrack(ticket.destination, usedTickets, route)

            remove ticket from route
            unmark ticket

sort all complete routes
return the smallest route

If there are E tickets, the search can explore up to E! ticket orders. Verifying or copying an itinerary adds another factor of E, producing a worst-case time complexity near:

O(E · E!)

With up to 300 tickets, this approach is impractical and can result in Time Limit Exceeded. The main issue is that it repeatedly constructs entire partial routes and explores many permutations that cannot lead to a better complete answer.

Algorithm Strategy: Stack Patterns

1. Create an adjacency structure mapping each departure airport to a min-heap of destination airports.
2. Insert every ticket into the heap belonging to its departure airport.
3. Start recursive traversal from "JFK".
4. While the current airport has unused destinations:
   • Remove the lexicographically smallest destination.
   • Recursively visit that destination.
5. Append the current airport to route after its destination heap is empty.
6. Reverse route.
7. Return the reversed sequence.

The heaps enforce lexicographically smallest local choices. The recursive call stack and postorder insertion enforce the global requirement that every ticket is used exactly once, including tickets involved in cycles or detours.

Execution Flow

1. Build ordered outgoing tickets

   • For each ticket [source, destination], insert destination into source’s min-heap.
   • Duplicate destinations remain as separate heap entries.

2. Begin at "JFK"

   • Call visit("JFK").

3. Consume the smallest available ticket

   • If "JFK" has destinations "BOS" and "LIM", the heap returns "BOS" first.
   • That ticket is removed immediately, so it cannot be reused.

4. Expand recursively

   • Call visit("BOS").
   • Continue consuming tickets from "BOS" before returning to the previous call.

5. Append airports during recursion unwinding

   • When an airport has no outgoing tickets left, append it to route.
   • A parent call resumes only after its recursive child has completed.

6. Reverse the completion order

   • Because airports were appended after their outgoing edges, route is in reverse itinerary order.
   • Reverse it to obtain the forward itinerary.

7. Use every ticket exactly once

   • Every ticket is removed from exactly one heap.
   • The problem guarantees that the traversal can consume all tickets, so the reversed route contains exactly tickets.length + 1 airports.

Proof of Correctness

Let visit(a) be the recursive procedure applied to airport a.

Claim 1: Every ticket is used at most once

Each ticket is represented by one entry in exactly one destination heap. The algorithm removes a heap entry before recursively visiting its destination. Removed entries are never inserted again, so no ticket can be used twice.

Claim 2: visit(a) consumes all outgoing tickets that belong in the traversal

The procedure repeatedly removes destinations while a’s heap is nonempty. Therefore, when visit(a) appends a, there are no remaining outgoing tickets from a in the data structure.

Because recursive calls are completed before the parent continues, all tickets reachable through selected destinations are processed before the parent airport is finalized.

Claim 3: The resulting sequence uses every ticket exactly once

The input guarantees that a complete itinerary exists. The traversal consumes each selected ticket once and records one airport for every recursive completion. Since the algorithm continues until the heaps are empty, all tickets are consumed. The route therefore contains exactly one more airport than the number of tickets and corresponds to a valid sequence of directed flights.

Claim 4: The final itinerary is lexicographically smallest

At every airport, the smallest currently available destination is removed first. If this choice enters a cycle or detour, postorder recording delays the corresponding airport’s final position until all required continuation tickets have been consumed. Thus, the algorithm does not prematurely finalize a locally small choice in a way that prevents using the remaining tickets.

At the first position where two valid itineraries differ, the algorithm selects the smallest available destination that can be included in the complete edge traversal. Therefore, no valid itinerary has a smaller airport at that position. Applying this argument from left to right proves that the reversed route is lexicographically smallest.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 735: Asteroid Collision
• LeetCode 394: Decode String
• LeetCode 1598: Crawler Log Folder
• LeetCode 71: Simplify Path

These problems use stack state to simulate nested or sequential operations. The current state is pushed or represented before deeper processing, then restored or finalized when processing returns. In LeetCode 332, the same stack-oriented behavior appears through recursive calls, edge consumption, and postorder route construction.

Reference Implementation

C++ Solution for LeetCode 332

1class Solution {
2    std::map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>> graph;
3    std::vector<std::string> route;
4
5    void visit(const std::string& airport) {
6        auto& destinations = graph[airport];
7        while (!destinations.empty()) {
8            std::string next = destinations.top();
9            destinations.pop();
10            visit(next);
11        }
12        route.push_back(airport);
13    }
14
15public:
16    vector<string> findItinerary(vector<vector<string>>& tickets) {
17        graph.clear();
18        route.clear();
19
20        for (const auto& ticket : tickets) {
21            graph[ticket[0]].push(ticket[1]);
22        }
23
24        visit("JFK");
25        std::reverse(route.begin(), route.end());
26        return route;
27    }
28};

The C++ implementation stores each airport’s destinations in a min-heap. visit consumes all destinations before appending the current airport, creating the required reverse postorder route.

Java Solution for LeetCode 332

1class Solution {
2    private java.util.Map<String, java.util.PriorityQueue<String>> graph;
3    private java.util.List<String> route;
4
5    public String[] findItinerary(String[][] tickets) {
6        graph = new java.util.HashMap<>();
7        
8        for (String[] ticket : tickets) {
9            graph.computeIfAbsent(ticket[0], k -> new java.util.PriorityQueue<>())
10                 .add(ticket[1]);
11        }
12
13        route = new java.util.ArrayList<>();
14        visit("JFK");
15
16        java.util.Collections.reverse(route);
17        return route.toArray(new String[0]);
18    }
19
20    private void visit(String airport) {
21        java.util.PriorityQueue<String> destinations = graph.get(airport);
22        if (destinations == null) {
23            destinations = new java.util.PriorityQueue<>();
24        }
25
26        while (!destinations.isEmpty()) {
27            visit(destinations.poll());
28        }
29
30        route.add(airport);
31    }
32}

The Java solution uses PriorityQueue<String> for lexicographical destination ordering. Each call removes destinations from the queue until none remain, then appends its airport to the route.

Python Solution for LeetCode 332

1import heapq
2
3class Solution:
4    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
5        graph = {}
6        for source, destination in tickets:
7            graph.setdefault(source, []).append(destination)
8
9        for destinations in graph.values():
10            heapq.heapify(destinations)
11
12        route = []
13
14        def visit(airport: str) -> None:
15            destinations = graph.get(airport, [])
16            while destinations:
17                visit(heapq.heappop(destinations))
18            route.append(airport)
19
20        visit("JFK")
21        return route[::-1]

The Python implementation converts every destination list into a heap with heapify. heappop removes the smallest available destination, and route[::-1] reverses the postorder completion sequence.