Given a list of airline tickets as [from, to] pairs, reconstruct the itinerary in order, starting from "JFK", using every ticket exactly once. If multiple valid itineraries exist, return the lexicographically smallest one.
This is really "find an Eulerian path" — a route that uses every edge (ticket) exactly once.
Greedily always taking the lexically smallest next destination can strand you at a dead end before all tickets are used — a plain greedy DFS isn't enough.
Hierholzer's algorithm sidesteps that: recurse first, then append the current airport to the route on the way back up (postorder), and reverse the finished route.
Step-by-Step Analysis
Build an adjacency map from airport to a min-heap of destinations, so the lexically smallest option is always available first.
Start a DFS from "JFK". At each airport, while it still has unused outgoing tickets, pop the smallest destination and recurse into it.
Once an airport has no more tickets left to use (a true dead end, reached only after exhausting every option), append it to the route.
Reverse the accumulated route at the end to get the itinerary in forward order.
Complexity
Time: O(E log E) for the heap operations across all tickets — Space: O(E)
Code
from collections import defaultdict
import heapq
def findItinerary(tickets: list[list[str]]) -> list[str]:
graph = defaultdict(list)
for src, dst in tickets:
heapq.heappush(graph[src], dst)
route = []
def visit(airport: str) -> None:
while graph[airport]:
next_dest = heapq.heappop(graph[airport])
visit(next_dest)
route.append(airport)
visit("JFK")
return route[::-1]
Code Explanation
How the solution above works, piece by piece.
Store each airport's destinations in a min-heap so they come out in lexical order, as the problem requires.
visit(airport) keeps using the smallest remaining ticket out of airport; each ticket is popped, so it's used exactly once.
Only when an airport has no tickets left is it appended to route. This post-order trick (Hierholzer's algorithm) handles detours: a dead end reached too early ends up at the end of the final route.
The route is built backwards, so return route[::-1].
O(E log E) for E tickets because of the heaps.
Visual Walkthrough
Running it on the example tickets:
The DFS always takes the alphabetically smallest unused ticket. An airport is added to route only when it has no tickets left, so the dead end SJC is added first and JFK last (badges). Reversing gives the itinerary.