Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

• For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]] Output: [“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

Example 2:

Input: tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]] Output: [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”] Explanation: Another possible reconstruction is [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] but it is larger in lexical order.

Constraints:

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• fromi.length == 3
• toi.length == 3
• fromi and toi consist of uppercase English letters.
• fromi != toi

Approach: Hierholzer’s Algorithm (Eulerian Path) with Backtracking

Algorithm

1. Build an adjacency map where each airport maps to a priority queue (min-heap) of destinations, so the lexicographically smallest destination is taken first
2. Run a post-order DFS from "JFK": at each airport, keep consuming the smallest available destination until no tickets remain
3. Append the airport to the result after all its destinations are exhausted, then reverse the list at the end

Time & Space Complexity

• Time Complexity: O(E log E) - E tickets; each heap pop costs O(log E), dominated by sorting destinations
• Space Complexity: O(E) - the adjacency structure and recursion depth

Java Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class ReconstructItinerary {

    private final Map<String, PriorityQueue<String>> graph = new HashMap<>();
    private final LinkedList<String> itinerary = new LinkedList<>();

    /**
     * Reconstruct the itinerary using all tickets exactly once.
     * @param tickets Flight tickets
     * @return The itinerary starting at "JFK"
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String from = ticket.get(0);
            String to = ticket.get(1);
            graph.computeIfAbsent(from, k -> new PriorityQueue<>()).offer(to);
        }

        dfs("JFK");
        return itinerary;
    }

    private void dfs(String airport) {
        PriorityQueue<String> destinations = graph.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll());
        }
        itinerary.addFirst(airport);
    }

    // Test method
    public static void main(String[] args) {
        ReconstructItinerary ri = new ReconstructItinerary();
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(List.of("JFK", "SFO"));
        tickets.add(List.of("JFK", "ATL"));
        tickets.add(List.of("SFO", "ATL"));
        tickets.add(List.of("ATL", "JFK"));
        tickets.add(List.of("ATL", "SFO"));
        System.out.println("Input: tickets = [[\"JFK\",\"SFO\"],[\"JFK\",\"ATL\"],[\"SFO\",\"ATL\"],[\"ATL\",\"JFK\"],[\"ATL\",\"SFO\"]]");
        System.out.println("Output: " + ri.findItinerary(tickets));
        // Expected: [JFK, ATL, JFK, SFO, ATL, SFO]
    }
}

Example Walkthrough

For tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]:

1. Adjacency (each destination in a min-heap):

• JFK: [ATL, SFO]
• SFO: [ATL]
• ATL: [JFK, SFO]

2. DFS from JFK: poll “ATL” (smallest). From ATL poll “JFK”. From JFK poll “SFO”. From SFO poll “ATL”. From ATL poll “SFO”. SFO has no more tickets.
3. Post-order adds airports in reverse: JFK, ATL, JFK, SFO, ATL, SFO

The greedy min-heap choice always preserves a valid Eulerian path because post-order insertion defers dead ends.

Key Points

1. Eulerian Path: The itinerary uses every edge (ticket) exactly once, a classic Eulerian trail problem
2. Min-Heap Destinations: Always try the smallest destination first to achieve lexical order
3. Post-Order Insertion: Adding the airport after consuming all descendants guarantees correctness even with dead ends
4. addFirst: Prepending builds the reversed path into the final itinerary
5. Guaranteed Validity: The problem guarantees at least one valid itinerary exists