Given a list of airline tickets [from, to], reconstruct the itinerary in lexicographical order starting from "JFK". Use all tickets exactly once.
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"]
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.
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)