A traveller's bag holds a pile of one-way boarding passes, each [origin, destination], with airports named by three uppercase letters. They want to know a route that flies every pass exactly once, one after another (each flight leaves from where the previous one landed). Nobody wrote down where the trip started.
Implement find_itinerary(tickets: list[list[str]]) -> list[str]: the airports of such a route in order (so len(tickets) + 1 of them), or [] if no route uses all the passes. The same pass can appear more than once, and each copy must be flown.
- Where to start: if some airport has one more departing pass than arriving passes, the route must start there. If every airport is balanced, the route is a round trip and may start anywhere.
- Which route: if several routes work, return the lexicographically smallest list of airports (compare the first airport, then the second, and so on). Since every code has three letters, this is the same as comparing the routes written as one string.
- Return
[]for an empty pile.
In the first example below, SFO is left twice but reached only once, so the route starts at SFO (and ATL, reached twice but left once, is where it ends). Going SFO ATL JFK first is smallest; from JFK the smaller choice ATL would strand the passes JFK->SFO and SFO->JFK, so the route must go JFK SFO JFK before finishing at ATL.
find_itinerary([["SFO", "JFK"], ["JFK", "ATL"], ["ATL", "JFK"], ["JFK", "SFO"], ["SFO", "ATL"]])
# ["SFO", "ATL", "JFK", "SFO", "JFK", "ATL"]
find_itinerary([["LAX", "DEN"], ["DEN", "LAX"]]) # ["DEN", "LAX", "DEN"] balanced: start at the smallest
find_itinerary([["AAA", "BBB"], ["CCC", "DDD"]]) # [] two separate pieces
find_itinerary([["AAA", "BBB"], ["AAA", "CCC"]]) # [] AAA can't be left twice
Up to 100,000 passes. Trying the smallest destination first and backtracking out of dead ends can take exponential time, and recursion that deep will overflow Python's stack.
Show hint
Walk greedily along the smallest unused pass, but don't treat getting stuck as failure: an airport you're stuck at belongs at the end of the part of the route still to be built. Recording airports as you back out of them (with an explicit stack) gives the route in reverse.