Reconstruct Itinerary

Description

Use every directed flight ticket exactly once to build an itinerary beginning at JFK. If multiple complete itineraries exist, return the lexicographically smallest. Assume a valid itinerary exists; duplicate tickets represent separate flights.

Solution

def find_itinerary(tickets):
    flights = {}
    for source, target in tickets:
        flights.setdefault(source, []).append(target)
    for destinations in flights.values():
        destinations.sort(reverse=True)
    stack, route = ["JFK"], []
    while stack:
        destinations = flights.get(stack[-1], [])
        if destinations:
            stack.append(destinations.pop())
        else:
            route.append(stack.pop())
    return route[::-1]

Examples

Approach

Sort each airport's destinations in reverse lexical order and remove the smallest from the end. Follow flights with a stack; when an airport has no unused outgoing ticket, append it to a reverse route. Reversing that route completes Hierholzer's Eulerian-path construction.