Reconstruct Itinerary

NeetCode: Reconstruct Itinerary · LeetCode: 332. Reconstruct Itinerary · Difficulty: Hard

You are given airline tickets as [from, to] pairs. Reconstruct the itinerary that starts at "JFK" and uses every ticket exactly once. If several itineraries exist, return the one with the smallest lexical order when read as a sequence of airport names. A valid itinerary is guaranteed to exist.

Example

Text

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]

The tickets are the edges of a directed graph, and the itinerary is a path that uses every edge exactly once, which is an Eulerian path. (A Hamiltonian path, which visits every vertex once, is a much harder problem.)

Brute force: backtracking over sorted tickets

Sort the tickets so that, from any airport, the destinations are tried in lexical order. Then extend the path one ticket at a time: pick the first unused ticket leaving the current airport, recurse, and undo the choice if it leads to a dead end. The first complete path found is the smallest one, because smaller destinations are always tried first.

Each ticket is a String[]{from, to}. The sort compares from first and to second with String.compareTo, which orders strings by their UTF-16 code units, so uppercase airport codes sort alphabetically.

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String[]> sorted = new ArrayList<>();
        for (List<String> t : tickets) sorted.add(new String[] {t.get(0), t.get(1)});
        sorted.sort((x, y) -> x[0].equals(y[0]) ? x[1].compareTo(y[1]) : x[0].compareTo(y[0]));
        boolean[] used = new boolean[sorted.size()];
        List<String> path = new ArrayList<>();
        path.add("JFK");
        dfs(sorted, used, path);
        return path;
    }

    private boolean dfs(List<String[]> tickets, boolean[] used, List<String> path) {
        if (path.size() == tickets.size() + 1) return true;
        String cur = path.get(path.size() - 1);
        for (int i = 0; i < tickets.size(); i++) {
            String[] t = tickets.get(i);
            if (used[i] || !t[0].equals(cur)) continue;
            // An identical unused earlier ticket would lead to the same subtree.
            if (i > 0 && !used[i - 1] && t[0].equals(tickets.get(i - 1)[0])
                    && t[1].equals(tickets.get(i - 1)[1])) {
                continue;
            }
            used[i] = true;
            path.add(t[1]);
            if (dfs(tickets, used, path)) return true;
            path.remove(path.size() - 1);
            used[i] = false;
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        List<List<String>> a = List.of(
                List.of("MUC", "LHR"), List.of("JFK", "MUC"), List.of("SFO", "SJC"), List.of("LHR", "SFO"));
        System.out.println(s.findItinerary(a));
        List<List<String>> b = List.of(
                List.of("JFK", "SFO"), List.of("JFK", "ATL"), List.of("SFO", "ATL"),
                List.of("ATL", "JFK"), List.of("ATL", "SFO"));
        System.out.println(s.findItinerary(b));
        System.out.println(s.findItinerary(List.of()));
    }
}

Output

[JFK, MUC, LHR, SFO, SJC]
[JFK, ATL, JFK, SFO, ATL, SFO]
[JFK]

Each step may try several tickets, and a wrong early choice (such as taking a dead-end airport too soon) is only discovered many steps later, so the search is exponential in the number of tickets in the worst case. Time: O(E^E) worst case, in practice much smaller. Space: O(E) for the recursion and used array.

Optimal: Hierholzer's algorithm

Hierholzer's algorithm builds an Eulerian path without backtracking over choices. Walk forward, always taking the smallest unused ticket. An airport with no unused tickets left is the end of the route (or of a closed loop that belongs earlier in it), so append it to the route and step back. The collected airports in reverse order form the itinerary.

To take the smallest destination quickly, each airport's destinations are stored in a PriorityQueue<String>, a min-heap, and taken with poll(). Each poll() costs O(log d) for d destinations at that airport. The stack is an ArrayDeque<String>.

Walkthrough of the second example: the stack grows to JFK -> ATL -> JFK -> SFO -> ATL -> SFO. The last SFO has no tickets left and is appended to the route, then the ATL below it, then SFO, and so on until the stack is empty. The route in reverse is JFK ATL JFK SFO ATL SFO.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    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), key -> new PriorityQueue<>()).add(t.get(1));
        }

        Deque<String> stack = new ArrayDeque<>();
        stack.push("JFK");
        List<String> route = new ArrayList<>();
        while (!stack.isEmpty()) {
            String top = stack.peek();
            PriorityQueue<String> next = graph.get(top);
            if (next != null && !next.isEmpty()) {
                stack.push(next.poll());
            } else {
                route.add(top);
                stack.pop();
            }
        }
        Collections.reverse(route);
        return route;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        List<List<String>> a = List.of(
                List.of("MUC", "LHR"), List.of("JFK", "MUC"), List.of("SFO", "SJC"), List.of("LHR", "SFO"));
        System.out.println(s.findItinerary(a));
        List<List<String>> b = List.of(
                List.of("JFK", "SFO"), List.of("JFK", "ATL"), List.of("SFO", "ATL"),
                List.of("ATL", "JFK"), List.of("ATL", "SFO"));
        System.out.println(s.findItinerary(b));
        System.out.println(s.findItinerary(List.of()));
    }
}

Output

[JFK, MUC, LHR, SFO, SJC]
[JFK, ATL, JFK, SFO, ATL, SFO]
[JFK]

Every ticket is pushed and popped once, plus the heap operations. Time: O(E log E). Space: O(E).