30 · Advanced Graphs: Euler Paths, Bridges & SCCs
#332 Reconstruct Itinerary
the problem
In plain words
You get a list of flight tickets; each [from, to] uses 3-letter airport codes. The traveller starts at JFK and must use every ticket exactly once. Return the trip as the list of airports in visiting order. If several trips work, return the one that comes first in dictionary order when you compare the airports one by one. A valid trip always exists.
in tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
out ["JFK","MUC","LHR","SFO","SJC"]
Only one order uses all four tickets.
in tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
out ["JFK","ATL","JFK","SFO","ATL","SFO"]
JFK, SFO, ATL, JFK, ATL, SFO also uses every ticket, but ATL < SFO at the second stop.
- 1 ≤ tickets.length ≤ 300
- Each code is 3 uppercase letters, and from ≠ to
- The same ticket may appear more than once
- At least one valid trip exists
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternEuler path (Hierholzer)Graph DFS / BFS traversal
where this runsShort-read genome assemblers such as Velvet are built on the Euler-path model: a de Bruijn graph of overlapping DNA pieces.
Airports are vertices and tickets are edges: "use every ticket once" is an Euler path. Hierholzer: always take the smallest unused ticket, and add an airport to the route only when you're stuck there — then reverse. A dead end is added first, so it lands at the end of the trip, and loops get spliced in before it.
solutions
From brute force to optimal
Sort each airport's destinations. Try them in order; if the route gets stuck before every ticket is used, give the ticket back and try the next one. The first complete route is the smallest.
- Build airport → sorted list of destinations.
- fly(from): if the route has E + 1 airports, done.
- For each destination in order (skipping repeats of the same one): remove it, append it, recurse; on failure, undo both.
A wrong early ticket may only fail much later, and every undo retries other orders. Sorting adds O(E log E).
The adjacency lists, the route, and recursion up to E deep.
class Solution { /** Try destinations in sorted order; give a ticket back when the route gets stuck. */ public List<String> findItinerary(List<List<String>> tickets) { Map<String, List<String>> next = new HashMap<>(); for (List<String> t : tickets) next.computeIfAbsent(t.get(0), k -> new ArrayList<>()).add(t.get(1)); for (List<String> list : next.values()) Collections.sort(list); List<String> route = new ArrayList<>(List.of("JFK")); fly("JFK", next, tickets.size() + 1, route); return route; } private boolean fly(String from, Map<String, List<String>> next, int stops, List<String> route) { if (route.size() == stops) return true; // every ticket is used List<String> out = next.getOrDefault(from, new ArrayList<>()); for (int i = 0; i < out.size(); i++) { if (i > 0 && out.get(i).equals(out.get(i - 1))) continue; // same ticket twice: same result String to = out.remove(i); // use the ticket route.add(to); if (fly(to, next, stops, route)) return true; route.remove(route.size() - 1); // dead end: undo out.add(i, to); } return false; }}visit(a): while a has unused tickets, poll the smallest and visit it. When a has none left, append a to the route. Reverse the route at the end.
- Build airport → PriorityQueue of destinations.
- visit(JFK).
- visit(a): while a's heap isn't empty: visit(heap.poll()). Then route.add(a).
- Collections.reverse(route).
Each ticket is offered to and polled from one heap exactly once; each heap operation is O(log E).
The heaps hold E tickets; the route and the recursion depth are at most E + 1.
class Solution { public List<String> findItinerary(List<List<String>> tickets) { Map<String, PriorityQueue<String>> next = new HashMap<>(); for (List<String> t : tickets) { next.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1)); } List<String> route = new ArrayList<>(); visit("JFK", next, route); Collections.reverse(route); // airports were added last-to-first return route; } private void visit(String airport, Map<String, PriorityQueue<String>> next, List<String> route) { PriorityQueue<String> out = next.get(airport); while (out != null && !out.isEmpty()) { String to = out.poll(); // smallest unused ticket from here visit(to, next, route); } route.add(airport); // stuck: nothing left to fly from here }}Dry run
The same post-order without recursion: peek the top airport; if it has a ticket left, push the destination; otherwise pop it into the route.
- Push JFK.
- Peek: if its heap isn't empty, push heap.poll().
- Else pop it and append to the route.
- Reverse the route.
Every ticket is pushed once and every airport visit popped once; heap work dominates.
Heaps, stack and route each hold at most E + 1 items.
class Solution { public List<String> findItinerary(List<List<String>> tickets) { Map<String, PriorityQueue<String>> next = new HashMap<>(); for (List<String> t : tickets) next.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1)); Deque<String> stack = new ArrayDeque<>(List.of("JFK")); List<String> route = new ArrayList<>(); while (!stack.isEmpty()) { PriorityQueue<String> out = next.get(stack.peek()); if (out != null && !out.isEmpty()) stack.push(out.poll()); // keep flying else route.add(stack.pop()); // stuck: this airport is final, counted from the end } Collections.reverse(route); return route; }}in the room
How to say it in the interview
talk track
- Say: "Airports are vertices, tickets are directed edges, and I must use every edge once — that's an Euler path from JFK."
- Show why greedy fails with JFK→KUL, JFK→NRT, NRT→JFK: KUL is smaller but a dead end.
- Explain Hierholzer: post-order — an airport is added when it's stuck — then reverse. The heaps make it the smallest route.
- Complexity: O(E log E) time, O(E) space. Mention the iterative version for very deep inputs.
traps
- Adding the airport on arrival (pre-order) instead of when stuck — dead ends end up in the middle.
- Using
Map<String, List<String>>andremove(0)— O(E) per ticket. Use aPriorityQueue. - Forgetting that the same ticket can appear twice — a
Setof destinations would silently drop one. - Returning before reversing — the route is built backwards.
what they ask next
Follow-ups
What if a valid trip is not guaranteed?
Check the degrees first (start has out − in = 1 or all balanced) and, after Hierholzer, that the route has E + 1 airports. If not, no trip uses every ticket.
Valid Arrangement of Pairs (LC 2097)?
Same Euler path with integer vertices and any valid order: find the start by degrees (out − in = 1, else any vertex), then Hierholzer without heaps.
Cracking the Safe (LC 753)?
A de Bruijn sequence: vertices are (n−1)-digit strings, each n-digit password is an edge. An Euler circuit types every password once in kⁿ + n − 1 key presses.
before you submit
Edge cases to test
- The smallest first hop is a dead end (JFK→KUL, JFK→NRT, NRT→JFK) → JFK, NRT, JFK, KUL.
- The same ticket twice (JFK→ATL twice and ATL→JFK) → both copies must be used.
- A single ticket → just [JFK, its destination].
- The trip may return to JFK and leave again — JFK can appear many times.
practise next
Similar problems
- #787Cheapest Flights Within K StopsMediumin Shortest Paths
- #210Course Schedule IIMediumin Topo Sort
- #46PermutationsMediumin Backtracking