Problem. Tickets represent directed flights. Starting from JFK, return the itinerary that uses every ticket exactly once and is lexicographically smallest among all valid answers.
This is the classic Eulerian path construction pattern.
Examples:
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]→["JFK","MUC","LHR","SFO","SJC"]tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]→["JFK","NRT","JFK","KUL"]- Every ticket must be consumed exactly once
Solution. Because every edge must be used exactly once, this is an Eulerian-path problem. Sorting destinations in reverse order lets a stack-style DFS pop the smallest lexical choice first after reversal of the final path.
from collections import defaultdict
def find_itinerary(tickets):
graph = defaultdict(list)
for source, target in sorted(tickets, reverse=True):
graph[source].append(target)
route = []
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop())
route.append(airport)
dfs('JFK')
return route[::-1]
O(E log E) time from sorting, O(E) recursion and storage.
Gotchas.
- A greedy lexical choice without Eulerian-path logic can get stuck too early.
- Append airports after exhausting outgoing edges, then reverse at the end.
- Sorting in reverse is a trick so
.pop()retrieves the smallest remaining destination.