tickets · green = used
adj · poll() takes the rightmost, smallest
dfs call stack · top at the right
res · post-order (stuck airports)
Route = res reversed · grows from the back
public List<String> findItinerary(List<List<String>> tickets) { Map<String, PriorityQueue<String>> adj = new HashMap<>(); for (List<String> t : tickets) { adj.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()) .add(t.get(1)); // min-heap: smallest dst first } List<String> res = new ArrayList<>(); dfs("JFK", adj, res); Collections.reverse(res); return res;}private void dfs(String src, Map<String, PriorityQueue<String>> adj, List<String> res) { PriorityQueue<String> q = adj.get(src); while (q != null && !q.isEmpty()) { String dst = q.poll(); dfs(dst, adj, res); } res.add(src); // stuck: no tickets left here}
- src
- —
- dst
- —
- depth
- 0
- tickets left
- —
Why it works
- Brute force backtracks: try destinations in alphabetical order and undo a choice that strands unused tickets. Correct, but it can redo work exponentially often on bad inputs.
- Using every ticket once is an Euler path. Hierholzer's idea: walk greedily, smallest destination first. When you get stuck, the airport you're stuck at must be the END of the remaining trip, so append it to
resand back up. - Post-order builds the route backwards. A dead end found early (KUL in the "dead end" preset) is appended first, so it lands last after reversing, while the detour through NRT gets spliced in front of it. Each ticket is popped once: O(E log E) for the heap operations, O(E) space.
- Pitfall: keep each airport's destinations in a
PriorityQueue, sopoll()gives the smallest in O(log k). AHashMapto a plain list would need a sort andremove(0), which is O(n). Repeated tickets are separate heap entries, so a multigraph just works. - Related: Valid Arrangement of Pairs (2097) is the same Euler path. Cheapest Flights (787) and Network Delay Time (743) use the same kind of flight graph with prices.