Turn tickets into sorted departure lists, always fly the smallest unused ticket, and fix each airport into the route only when it runs dry.
Fly the smallest ticket first, and write each airport down only when it has no tickets left — then read the list backwards.
A greedy smallest-first walk can strand tickets: flying JFK → KUL early leaves NRT → JFK unusable. The fix is to record airports post-order — an airport joins the route only after every ticket out of it is consumed.
Each frame flies one ticket or fixes one airport. Green stack airports still hold unused tickets; the red ghost is the airport just fixed; the final lime row is the reversed route.
from collections import defaultdict
def findItinerary(tickets):
graph = defaultdict(list)
for src, dst in tickets:
graph[src].append(dst)
for src in graph:
graph[src].sort(reverse=True) # smallest leaves via pop()
route, stack = [], ["JFK"]
while stack:
while graph[stack[-1]]: # fly smallest unused ticket
stack.append(graph[stack[-1]].pop())
route.append(stack.pop()) # dead end: fix into route
return route[::-1] # built backwardsThe inner while looks nested, but each ticket is popped exactly once; sorting the departure lists dominates the runtime.
pop() from a reverse-sorted listSorting descending makes every departure choice O(1) while still picking the lexical minimum.append only when graph[top] is emptyAn airport enters the route only after all its departures are consumed — the post-order invariant.route[::-1]Fixes happen from the trip end backwards, so one reversal yields JFK-first order.JFK → SFO looks tempting but post-order buries it: ATL legs resolve first and the reversal restores lexical order.
Greedy smallest-first flies JFK → KUL and strands a ticket; fixing dead ends first forces NRT before KUL.
I sort every airport’s departures, always fly the smallest unused ticket, and only record an airport once it is out of tickets. The record comes out backwards, so I reverse it — that reversal is what guarantees I use every ticket in lexical order.