199. Reconstruct Itinerary

Why this mechanism works

A naive greedy route can reach a dead end too early. Hierholzer's method consumes edges while deferring a vertex's final placement until it has no outgoing tickets left. Sorting outgoing destinations in reverse permits efficient removal of the smallest one; reversing the completed postorder stitches detours into a full Euler route.

State and boundaries

stack is the current unfinished walk. adj contains unconsumed tickets. reverse_route collects vertices only after their outgoing tickets are exhausted.

Protocol

1. Build reverse-sorted destination lists.
2. Start a stack at the requested airport.
3. Follow and remove the smallest available outgoing ticket.
4. When none remains, pop that airport into reverse_route.
5. Reverse the completed route.

Visualization

tickets JFK->KUL, JFK->NRT, NRT->JFK
KUL is explored first but finishes first
reverse postorder -> JFK,NRT,JFK,KUL
the dead end belongs at the end

Python implementation

from collections import defaultdict

def reconstruct_itinerary(tickets, start='JFK'):
    adj = defaultdict(list)
    for origin, destination in tickets:
        adj[origin].append(destination)
    for destinations in adj.values():
        destinations.sort(reverse=True)
    stack, reverse_route = [start], []
    while stack:
        if adj[stack[-1]]:
            stack.append(adj[stack[-1]].pop())
        else:
            reverse_route.append(stack.pop())
    return reverse_route[::-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 reconstruct_itinerary: adj = defaultdict(list)
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={}

L5 reconstruct_itinerary: for origin, destination in tickets:
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={}; origin='JFK'; destination='KUL'

L6 reconstruct_itinerary: adj[origin].append(destination)
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL']}; origin='JFK'; destination='KUL'

L5 reconstruct_itinerary: for origin, destination in tickets:
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL']}; origin='JFK'; destination='NRT'

L6 reconstruct_itinerary: adj[origin].append(destination)
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL', 'NRT']}; origin='JFK'; destination='NRT'

L5 reconstruct_itinerary: for origin, destination in tickets:
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL', 'NRT']}; origin='NRT'; destination='JFK'

L6 reconstruct_itinerary: adj[origin].append(destination)
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL', 'NRT'], 'NRT':['JFK']}; origin='NRT'; destination='JFK'

L7 reconstruct_itinerary: for destinations in adj.values():
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':['KUL', 'NRT'], 'NRT':['JFK']}; origin='NRT'; destination='JFK'; destinations=['KUL', 'NRT']

... 7 intermediate state changes omitted ...

L12 reconstruct_itinerary: stack.append(adj[stack[-1]].pop())
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':[], 'NRT':[], 'KUL':[]}; origin='NRT'; destination='JFK'; destinations=[]; stack=['JFK', 'NRT', 'JFK']; reverse_route=['KUL']

L14 reconstruct_itinerary: reverse_route.append(stack.pop())
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':[], 'NRT':[], 'KUL':[]}; origin='NRT'; destination='JFK'; destinations=[]; stack=['JFK', 'NRT']; reverse_route=['KUL', 'JFK']

L14 reconstruct_itinerary: reverse_route.append(stack.pop())
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':[], 'NRT':[], 'KUL':[]}; origin='NRT'; destination='JFK'; destinations=[]; stack=['JFK']; reverse_route=['KUL', 'JFK', 'NRT']

L14 reconstruct_itinerary: reverse_route.append(stack.pop())
tickets=[('JFK', 'KUL'), ('JFK', 'NRT'), ('NRT', 'JFK')]; start='JFK'; adj={'JFK':[], 'NRT':[], 'KUL':[]}; origin='NRT'; destination='JFK'; destinations=[]; stack=[]; reverse_route=['KUL', 'JFK', 'NRT', 'JFK']

L4 reconstruct_itinerary: adj = defaultdict(list)
tickets=[]; start='SIN'; adj={}

L9 reconstruct_itinerary: stack, reverse_route = [start], []
tickets=[]; start='SIN'; adj={}; stack=['SIN']; reverse_route=[]

L11 reconstruct_itinerary: if adj[stack[-1]]:
tickets=[]; start='SIN'; adj={'SIN':[]}; stack=['SIN']; reverse_route=[]

L14 reconstruct_itinerary: reverse_route.append(stack.pop())
tickets=[]; start='SIN'; adj={'SIN':[]}; stack=[]; reverse_route=['SIN']

Why the solution is correct

Each ticket is removed once, and postorder splices completed trails into their shared vertices, yielding an Euler route under the existence precondition. Smallest-first exploration gives lexical priority to smaller feasible outgoing choices; a premature dead-end segment is placed at the route's end by postorder rather than blocking remaining tickets.

Time and space

O(E log E) sorting time and O(E) traversal time/space, including the E+1 airport output.

Common mistakes

Appending airports directly to the final forward route can strand unused tickets. Deduplicating repeated tickets loses required edge occurrences. Invalid-input detection is outside the guaranteed-existence contract.

Reasoning card

Transfer exercise

Remove the existence guarantee and validate the final consecutive airport pairs against the original ticket multiset.