221. Reconstruct Itinerary

Using every ticket exactly once is an Eulerian path. Greedily walk to the smallest available destination; when stuck, that airport is appended to the route. Reversing the collected order yields the itinerary.

An Eulerian path

Each ticket is a directed edge that must be traversed exactly once — that's an Eulerian path starting at JFK. Hierholzer's algorithm builds it:

1. For each airport keep its destinations sorted (so we always take the lexicographically smallest next).
2. DFS greedily: from the current airport follow edges until none remain (a dead end).
3. When stuck, prepend the current airport to the route (or append and reverse at the end).

for from, to in sorted(tickets): graph[from].append(to)   # smallest last for pop
stack = ['JFK']; route = []
while stack:
    while graph[stack[-1]]: stack.append(graph[stack[-1]].pop())
    route.append(stack.pop())
return route[::-1]

Worked example

[[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]] → [JFK, ATL, JFK, SFO, ATL, SFO].

Complexity

• Time: O(E log E) for sorting edges.
• Space: O(E).

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (String[] t : tickets) {
            graph.computeIfAbsent(t[0], z -> new PriorityQueue<>()).offer(t[1]);
        }
        LinkedList<String> route = new LinkedList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push("JFK");
        while (!stack.isEmpty()) {
            String airport = stack.peek();
            PriorityQueue<String> dests = graph.get(airport);
            if (dests != null && !dests.isEmpty()) {
                stack.push(dests.poll());
            } else {
                route.addFirst(stack.pop());
            }
        }
        return route;
    }
}