Reconstruct Itinerary

Given a list of airline tickets [from, to], reconstruct the itinerary in lexicographical order starting from "JFK". Use all tickets exactly once.

Example 1

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

Example 2

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

Solution Approach

Hierholzer's algorithm: DFS using a min-heap at each node (for lexicographic order). When a node has no outgoing edges, prepend it to the result.

Build adjacency list with min-heaps (PriorityQueue) for each airport.
DFS from JFK: while heap for current node non-empty, pop smallest and recurse.
After recursion returns, prepend current node to result.
Reverse result at end.

Java

import java.util.*;

class Solution {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    LinkedList<String> result = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets)
            graph.computeIfAbsent(t.get(0), k->new PriorityQueue<>()).offer(t.get(1));
        dfs("JFK");
        return result;
    }

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

Time Complexity: O(E log E). Heap operations
Space Complexity: O(V+E)