The problem
Given airline tickets as [from, to], rebuild the itinerary that uses every ticket exactly once, starting from JFK. If several work, return the one that is alphabetically smallest.
Input: JFK-SFO, JFK-ATL, SFO-ATL, ATL-JFK, ATL-SFO Output: [JFK, ATL, JFK, SFO, ATL, SFO]
Picture it
Picture a traveller holding a stack of plane tickets. At each airport they use the alphabetically earliest unused ticket. If they get stuck at an airport with no tickets left, that airport must be the end of the remaining trip, so they write it down and back up. Reading the written list backwards gives the itinerary.
How to recognise it
- You must use every edge exactly once (every ticket), not visit every node.
- The tickets form a directed graph, and the answer is one route through all of them: an Eulerian path.
- Several routes may exist, and you must return the smallest in a given order (alphabetical here).
- A greedy "take the smallest ticket" can get stuck at an airport with no way out while tickets remain elsewhere.
Start with brute force
Backtrack. From the current airport try the tickets in sorted order. If a choice leads to a dead end before all tickets are used, undo it and try the next one. The first complete route found is the smallest.
def find_itinerary_brute(tickets):
ts = sorted(tickets)
used = [False] * len(ts)
route = ["JFK"]
def go(city):
if len(route) == len(ts) + 1:
return True
for i, (a, b) in enumerate(ts):
if used[i] or a != city:
continue
if i and ts[i] == ts[i - 1] and not used[i - 1]:
continue # skip a duplicate ticket
used[i] = True
route.append(b)
if go(b):
return True
route.pop()
used[i] = False
return False
go("JFK")
return route
Each call scans all E tickets, and in a bad case the search undoes long stretches of the route and re-explores them, so the worst case grows exponentially with the number of tickets (up to E! orders). With E up to 300 that is not acceptable. Space is O(E).
From brute force to the idea
- Find the waste. Backtracking discovers a dead end, throws away a long prefix, and then rebuilds nearly the same prefix.
- A dead end is not a failure. Because a valid route exists, an airport where you get stuck must be the final stop of the route that remains to be built. Put it at the end and carry on.
- Walk greedily with sorted tickets. The code sorts tickets in reverse and appends each destination to a list, so
pop()gives the alphabetically smallest unused ticket from an airport. - Record stops on the way back.
flykeeps using tickets while the airport has any. Only when it is stuck does it doroute.append(airport). This is Hierholzer's algorithm: stops are written from the end of the trip towards the start. - Reverse once. The list is built back to front, so
route[::-1]is the itinerary.
The key idea: get stuck, write the stuck airport at the end, and keep going from where you were.
The key idea
Hierholzer’s algorithm for an Eulerian path: DFS with sorted tickets, append a node when stuck, reverse at the end.
Python solution
def find_itinerary(tickets):
out = defaultdict(list)
for a, b in sorted(tickets, reverse=True):
out[a].append(b) # pop() gives the smallest
route = []
def fly(airport):
while out[airport]:
fly(out[airport].pop()) # use a ticket
route.append(airport) # stuck here: finalise this stop
fly("JFK")
return route[::-1]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Backtracking | Exponential in the worst case: dead ends undo and redo long routes | O(E): the route and used flags |
| Hierholzer (shown code) | O(E log E): sorting dominates; each ticket is popped exactly once | O(E): the ticket lists and route, plus a recursion stack as deep as E |
Edge cases
- One ticket (
[["JFK","SFO"]]): returns["JFK","SFO"]. - A dead end that must come last (
JFK→KUL,JFK→NRT,NRT→JFK): returnsJFK, NRT, JFK, KUL. Taking KUL first would strand the other tickets. - Duplicate tickets (two
JFK→Atickets): each is used once. - Recursion depth:
flyrecurses once per ticket on the current route. It runs with 280 tickets, but a list of 2,000 tickets raisesRecursionErrorunder Python's default limit of 1,000. - Invalid input: the code assumes that a route through all tickets exists. If it does not, it returns something shorter or wrong instead of reporting an error.
- The input list is not modified.
defaultdictmust be imported.
Common mistakes
- Taking the smallest ticket greedily without handling dead ends, which can strand tickets.
- Appending to the route before the airport is stuck, which builds it in the wrong order.
- Forgetting to reverse, or sorting without
reverse=Truesopop()returns the largest ticket. - Treating airports as visited once, when an airport can be passed several times.
- Rebuilding the ticket list after every flight, which turns a constant-time step into O(E).
Return the alphabetically largest itinerary that uses every ticket. Describe what changes, then write it if you like.
Compare with our answer
Only the order of choosing tickets changes. Sort ascending instead of descending, so pop() returns the largest destination first.
def find_itinerary_largest(tickets):
out = defaultdict(list)
for a, b in sorted(tickets):
out[a].append(b) # pop() gives the largest
route = []
def fly(airport):
while out[airport]:
fly(out[airport].pop())
route.append(airport)
fly("JFK")
return route[::-1]
For tickets JFK→A, JFK→B, A→JFK, B→JFK it returns JFK, B, JFK, A, JFK. Time O(E log E), space O(E).
A strong answer mentions: that only the sort direction changes, why the dead-end logic still works, and the same complexity.
1. You have a set of dominoes, each showing two numbers. You must place all of them in one line, each exactly once, so that touching halves show the same number. Which approach fits best?
Using every edge exactly once is an Eulerian path, and Hierholzer's algorithm finds one in O(E). Dominoes can form loops, so a topological sort does not apply, and BFS or Dijkstra do not use every edge.
2. Why does fly append an airport only after its while loop, and why is the list reversed at the end?
When an airport has no tickets left, whatever remains of the trip must end there. Stops are therefore found from the end towards the start, and one reverse puts them in travel order.
3. A learner changes sorted(tickets, reverse=True) to sorted(tickets). Which input now returns a wrong itinerary?
Ticket order only matters when more than one valid route exists. The last input has two, and the changed sort picks B first, giving JFK, B, JFK, A, JFK. In the other inputs only one route is possible, so the order of choosing cannot change the result.
Score 60% or more and the lesson is marked complete.