LeetCode 332 · Advanced Graphs

Reconstruct Itinerary, explained with a picture

Using every plane ticket exactly once.

HardAdvanced Graphs
▶ Watch it step by step

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

  1. Find the waste. Backtracking discovers a dead end, throws away a long prefix, and then rebuilds nearly the same prefix.
  2. 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.
  3. 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.
  4. Record stops on the way back. fly keeps using tickets while the airport has any. Only when it is stuck does it do route.append(airport). This is Hierholzer's algorithm: stops are written from the end of the trip towards the start.
  5. 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

ApproachTimeSpace
BacktrackingExponential in the worst case: dead ends undo and redo long routesO(E): the route and used flags
Hierholzer (shown code)O(E log E): sorting dominates; each ticket is popped exactly onceO(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): returns JFK, NRT, JFK, KUL. Taking KUL first would strand the other tickets.
  • Duplicate tickets (two JFK→A tickets): each is used once.
  • Recursion depth: fly recurses once per ticket on the current route. It runs with 280 tickets, but a list of 2,000 tickets raises RecursionError under 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. defaultdict must 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=True so pop() 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).
Your turn: the largest itinerary

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.

Check what stuck

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?

2. Why does fly append an airport only after its while loop, and why is the list reversed at the end?

3. A learner changes sorted(tickets, reverse=True) to sorted(tickets). Which input now returns a wrong itinerary?

Score 60% or more and the lesson is marked complete.