Builds on Flood Fill, which you haven’t finished yet.
Eulerian Path (Hierholzer's Algorithm)
Return the airports of one trip, in order, that begins at "JFK" and uses every ticket in tickets exactly once. A ticket [fromi, toi] is one flight from airport fromi to airport toi, and every airport is written as 3 uppercase letters.
More than one trip can use all the tickets. Return the one whose list of airports comes first when the lists are compared airport by airport ("ATL" before "SFO"), which is the same as comparing each trip written as one string. The tickets always allow at least one such trip.
Eulerian Path
edges ➔ walk and delete each used edge ➔ nodes appended when stuck, then reversed| 1 | from collections import defaultdict |
| 2 | from typing import Hashable, List |
| 3 | |
| 4 | def eulerian_path(edges: List[List[Hashable]]) -> List[Hashable]: |
| 5 | """Eulerian Path (Hierholzer's algorithm, the core of Reconstruct Itinerary): the |
| 6 | smallest walk that uses every directed edge exactly once. |
| 7 | Time: O(E log E) | Space: O(E) |
| 8 | """ |
| 9 | graph = defaultdict(list) |
| 10 | balance = defaultdict(int) # out-degree minus in-degree |
| 11 | # reverse order, so pop() takes the smallest neighbour |
| 12 | for u, v in sorted(edges, reverse=True): |
| 13 | graph[u].append(v) |
| 14 | balance[u] += 1 |
| 15 | balance[v] -= 1 |
| 16 | # one extra edge out starts the path; a circuit starts at the smallest node |
| 17 | start = next((x for x in graph if balance[x] == 1), min(graph)) |
| 18 | path, stack = [], [start] |
| 19 | while stack: |
| 20 | node = stack[-1] |
| 21 | if graph[node]: |
| 22 | stack.append(graph[node].pop()) # follow an unused edge and delete it |
| 23 | else: |
| 24 | # no edge left: node is final in the rest of the walk |
| 25 | path.append(stack.pop()) |
| 26 | return path[::-1] # nodes were finished last-first |
stack is a walk from start over used edges, and path holds, last-first, the part of the Eulerian path that is already final.Walk from start, deleting each edge as you follow it with stack.append(graph[node].pop()), and add a node to path only when it has no unused edge left, with path.append(stack.pop()); reversing path gives the walk. This is correct because a walk that always takes some unused edge can only get stuck at the node where the whole path must end, so the first node to run out of edges is the last node of the answer; any cycle the walk skipped hangs off a node that is still on stack, and it is walked, and placed, when the stack backs up to that node. The trap is writing a node into the answer when you first reach it: the walk can enter the final dead end before a cycle has been used (in Reconstruct Itinerary (LC 332), taking the smallest airport first can strand the tickets of a loop), so a node goes into path only once its edges are used up, and the list is reversed at the end.
See it run
Hierholzer's walk, step by step
unused 10path []
Each circle is an airport and each arrow is an unused ticket. A ticket disappears from the picture after the step that uses it. The rows under the graph are stack and path.
nowthe airport on top of stack, or the ticket just usedstackan airport on the current walkfinalan airport already moved to path
JFK has one more ticket going out than coming in, so the walk must start there. Put JFK on stack.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing each node into the answer when first reached
Mistakepath.append(node) while graph[node]: node = graph[node].pop() path.append(node)Fixif graph[node]: stack.append(graph[node].pop()) else: path.append(stack.pop())What happens: The walk can enter the final dead end before a cycle has been used. Written in the order reached, the answer stops at that dead end. The cycle's edges are never used. The blueprint adds a node to
pathonly when its edges are used up, then reversespath.Example: Reconstruct Itinerary (LC 332): tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]Mistake: returns ['JFK', 'KUL']Fix: returns ['JFK', 'NRT', 'JFK', 'KUL']
- Every node must appear once, after everything it depends on, as in Course Schedule II (LC 210): that is an order of the nodes, not a walk over every edge. See Topological Sort
- You only need to know which nodes the edges join, as in Number of Provinces (LC 547), not an order in which to use each edge. See Flood Fill
Deep Dive
Why a node is final only when its tickets run out
An Eulerian path is a walk that uses every edge exactly once. In Reconstruct Itinerary (LC 332), each ticket is an edge, and the itinerary must use every ticket once. Hierholzer's algorithm builds the walk with one stack and one path.
The loop looks at the top of stack. If that airport has an unused ticket, the loop deletes the ticket with graph[node].pop() and pushes the airport it leads to. If the airport has no unused ticket, the loop moves it from stack to path.
The first airport that runs out of tickets is the last stop of the itinerary. The reason is a count. Every airport except the start and the end has as many tickets out as in. Each time the walk enters such an airport, it uses one ticket in, so one ticket out is still left. The walk can only get stuck at the end airport.
The walk may leave some tickets unused. Those tickets form loops that start and end at an airport already on stack. When the loop backs up to such an airport, it walks the loop, and the loop is placed in the right spot, because its airports reach path before the airports under them.
Example: for tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]], the smallest-first walk goes JFK -> KUL and gets stuck, with the loop JFK -> NRT -> JFK still unused. The correct itinerary is ["JFK", "NRT", "JFK", "KUL"].
One trace: ten tickets, one dead end, two loops
The board uses 10 tickets and 8 airports. The airport JFK is the start, because it has one more ticket out than in. The airport KUL is a dead end with no ticket out. The tickets are JFK -> ATL, ATL -> ORD, ORD -> JFK, JFK -> KUL, JFK -> NRT, NRT -> SFO, SFO -> ICN, ICN -> NRT, NRT -> LAX and LAX -> JFK.
The walk goes JFK, ATL, ORD, JFK. At JFK the smallest unused ticket goes to KUL, so the walk goes there and gets stuck. KUL moves to path. This is the first dead end, and KUL is the last stop.
The loop backs up to JFK, which still has a ticket to NRT. The walk goes NRT, LAX, JFK and gets stuck again, because JFK has no ticket left. JFK and LAX move to path. At NRT, the ticket to SFO is still unused. The walk goes SFO, ICN, NRT, and then everything moves to path in turn.
The final path is [KUL, JFK, LAX, NRT, ICN, SFO, NRT, JFK, ORD, ATL, JFK]. Reversed, it is [JFK, ATL, ORD, JFK, NRT, SFO, ICN, NRT, LAX, JFK, KUL]. The board uses 10 steps that delete a ticket and 11 steps that move an airport to path.
The traps: writing on arrival, the start, the sort and the reversal
Do not write an airport into the answer when you first reach it. On the board tickets, the greedy walk goes JFK, ATL, ORD, JFK, KUL and stops, because it is stuck at KUL. It used 4 of the 10 tickets. The blueprint writes an airport only when its tickets are used up, so the loops are not lost.
The start must be the airport with balance[x] == 1. For edges = [[1, 0], [0, 2]], the correct walk is [1, 0, 2]. Starting at the smallest node, 0, gives [0, 2] and leaves the ticket 1 -> 0 unused. Only when every airport is balanced is the path a circuit, and then it starts at min(graph).
The tickets are sorted with reverse=True, so pop() takes the smallest neighbour in O(1). With an ascending sort, pop() takes the largest. On the board tickets, the ascending sort gives [JFK, NRT, SFO, ICN, NRT, LAX, JFK, ATL, ORD, JFK, KUL]. This is a valid walk, but the correct answer goes JFK, ATL and not JFK, NRT.
The last line is path[::-1]. Airports reach path last-first. Without the reversal, the example [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] returns [SJC, SFO, LHR, MUC, JFK] and not [JFK, MUC, LHR, SFO, SJC].
The cost, and the neighbours
Sorting the tickets costs O(E log E). The walk then deletes each ticket once and moves each airport to path once, which is O(E). The total is O(E log E) time. graph, balance, stack and path hold O(E) entries, so the space is O(E).
On the board, 10 tickets give 11 airports in the answer. Each ticket is deleted in one step, and each of the 11 stops reaches path in one step.
The same walk solves Valid Arrangement of Pairs (LC 2097), where the pairs are the edges and any valid order is accepted. Cracking the Safe (LC 753) uses it on a graph whose nodes are strings, and the walk gives the shortest string that contains every combination.
The Topological Sort card solves a different question. In Course Schedule II (LC 210), every node appears once, after everything it depends on. That is an order of the nodes. Here every edge is used once, and a node can appear many times. If you only need to know which nodes are joined, a plain search is enough, as in Number of Provinces (LC 547).
60-Second Pitch
"Every ticket must be used once, so this is an Eulerian path, and I use Hierholzer's algorithm. I sort the tickets in reverse and keep them in a list for each airport, so pop() takes the smallest destination. I start at the airport with one more ticket out than in, or at the smallest airport if all are balanced. I keep a stack. If the top airport has an unused ticket, I delete it and push the destination. If it has none, I move the airport to path. An airport goes into path only when its tickets are used up. So a dead end is placed last, and a loop that the walk skipped is walked when the stack backs up to its airport. At the end I return path reversed. Sorting costs O(E log E), and the walk costs O(E). The space is O(E)."
Common Questions
- Why does the walk get stuck only at the end airport?
Every airport except the start and the end has as many tickets out as in. Each entry into such an airport uses one ticket in, so one ticket out is still unused. The start has one extra ticket out. So the only airport where the walk can run out of tickets is the end.
- Why do you add an airport to
pathwhen it is stuck, and not when it is reached? The first stuck airport is the last stop. A loop that the walk skipped starts and ends at an airport that is still on
stack. If airports were written on arrival, the dead end would be written before the loop, and the loop would be lost. With the stuck rule, the loop is walked and placed before the airports under it.- How do you get the smallest itinerary?
Sort the tickets in reverse and use
pop(), so each airport always takes its smallest unused destination first. Hierholzer's algorithm with this rule returns the smallest valid walk for Reconstruct Itinerary (LC 332).- What are the time and space complexity?
O(E log E) time, because of the sort, and O(E) space. The walk itself deletes each ticket once and moves each airport to
pathonce.- How do you know that a valid walk exists?
Check the counts. In a directed graph, an Eulerian path needs every airport balanced, except at most one with one more ticket out than in (the start) and one with one more ticket in than out (the end). The edges must also be joined in one piece. Reconstruct Itinerary (LC 332) promises that a valid itinerary exists.
SWE Reasoning
Spot it
- Every ticket, domino, pair or transition must be used exactly once in one walk.
- The question asks for the walk or the order of the stops, and not only whether it exists.
- The wording says itinerary, arrangement, or the shortest string that contains every combination.
- When two choices are possible, the smallest one must win, so the neighbours are sorted.
- Trying every order of the edges would take O(E!) time, which is far too slow.
The invariant, step by step
- The tickets are sorted in reverse order, so
graph[u].pop()takes the smallest neighbour ofu. startis the airport withbalance[x] == 1. If every airport is balanced,startis the smallest airport.- The loop looks at
node = stack[-1]. Ifgraph[node]is not empty, it deletes the smallest ticket withpop()and pushes the airport it leads to. - If
graph[node]is empty, the loop movesnodefromstacktopath. No edge leaves this airport any more, so it is final in the rest of the walk. stackis always a walk fromstartover used tickets, andpathholds the final part of the answer, last-first.- When
stackis empty, every ticket was used.path[::-1]is the itinerary.
Traps
- Writing an airport into the answer when it is first reached. The walk can enter the final dead end before a loop is used, and the loop is lost. Add an airport to
pathonly when its tickets run out. - Starting at the smallest airport. A walk that is not a circuit must start at the airport with
balance[x] == 1. - Sorting ascending. Then
pop()takes the largest neighbour, and the walk is not the smallest one. Sort withreverse=True. - Using
pop(0)for the smallest neighbour. It moves every other item, so each step costs O(E). Sort in reverse and usepop(). - Returning
pathwithout reversing it. Airports reachpathlast-first. Returnpath[::-1].
Practice
Builds on Flood Fill, which you haven’t finished yet.
Eulerian Path (Hierholzer's Algorithm)
Return the airports of one trip, in order, that begins at "JFK" and uses every ticket in tickets exactly once. A ticket [fromi, toi] is one flight from airport fromi to airport toi, and every airport is written as 3 uppercase letters.
More than one trip can use all the tickets. Return the one whose list of airports comes first when the lists are compared airport by airport ("ATL" before "SFO"), which is the same as comparing each trip written as one string. The tickets always allow at least one such trip.
Eulerian Path
edges ➔ walk and delete each used edge ➔ nodes appended when stuck, then reversed| 1 | from collections import defaultdict |
| 2 | from typing import Hashable, List |
| 3 | |
| 4 | def eulerian_path(edges: List[List[Hashable]]) -> List[Hashable]: |
| 5 | """Eulerian Path (Hierholzer's algorithm, the core of Reconstruct Itinerary): the |
| 6 | smallest walk that uses every directed edge exactly once. |
| 7 | Time: O(E log E) | Space: O(E) |
| 8 | """ |
| 9 | graph = defaultdict(list) |
| 10 | balance = defaultdict(int) # out-degree minus in-degree |
| 11 | # reverse order, so pop() takes the smallest neighbour |
| 12 | for u, v in sorted(edges, reverse=True): |
| 13 | graph[u].append(v) |
| 14 | balance[u] += 1 |
| 15 | balance[v] -= 1 |
| 16 | # one extra edge out starts the path; a circuit starts at the smallest node |
| 17 | start = next((x for x in graph if balance[x] == 1), min(graph)) |
| 18 | path, stack = [], [start] |
| 19 | while stack: |
| 20 | node = stack[-1] |
| 21 | if graph[node]: |
| 22 | stack.append(graph[node].pop()) # follow an unused edge and delete it |
| 23 | else: |
| 24 | # no edge left: node is final in the rest of the walk |
| 25 | path.append(stack.pop()) |
| 26 | return path[::-1] # nodes were finished last-first |
stack is a walk from start over used edges, and path holds, last-first, the part of the Eulerian path that is already final.Walk from start, deleting each edge as you follow it with stack.append(graph[node].pop()), and add a node to path only when it has no unused edge left, with path.append(stack.pop()); reversing path gives the walk. This is correct because a walk that always takes some unused edge can only get stuck at the node where the whole path must end, so the first node to run out of edges is the last node of the answer; any cycle the walk skipped hangs off a node that is still on stack, and it is walked, and placed, when the stack backs up to that node. The trap is writing a node into the answer when you first reach it: the walk can enter the final dead end before a cycle has been used (in Reconstruct Itinerary (LC 332), taking the smallest airport first can strand the tickets of a loop), so a node goes into path only once its edges are used up, and the list is reversed at the end.
See it run
Hierholzer's walk, step by step
unused 10path []
Each circle is an airport and each arrow is an unused ticket. A ticket disappears from the picture after the step that uses it. The rows under the graph are stack and path.
nowthe airport on top of stack, or the ticket just usedstackan airport on the current walkfinalan airport already moved to path
JFK has one more ticket going out than coming in, so the walk must start there. Put JFK on stack.
Gotcha 1 of 4
- The trap
Gotcha 1: Writing each node into the answer when first reached
Mistakepath.append(node) while graph[node]: node = graph[node].pop() path.append(node)Fixif graph[node]: stack.append(graph[node].pop()) else: path.append(stack.pop())What happens: The walk can enter the final dead end before a cycle has been used. Written in the order reached, the answer stops at that dead end. The cycle's edges are never used. The blueprint adds a node to
pathonly when its edges are used up, then reversespath.Example: Reconstruct Itinerary (LC 332): tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]Mistake: returns ['JFK', 'KUL']Fix: returns ['JFK', 'NRT', 'JFK', 'KUL']
- Every node must appear once, after everything it depends on, as in Course Schedule II (LC 210): that is an order of the nodes, not a walk over every edge. See Topological Sort
- You only need to know which nodes the edges join, as in Number of Provinces (LC 547), not an order in which to use each edge. See Flood Fill
Deep Dive
Why a node is final only when its tickets run out
An Eulerian path is a walk that uses every edge exactly once. In Reconstruct Itinerary (LC 332), each ticket is an edge, and the itinerary must use every ticket once. Hierholzer's algorithm builds the walk with one stack and one path.
The loop looks at the top of stack. If that airport has an unused ticket, the loop deletes the ticket with graph[node].pop() and pushes the airport it leads to. If the airport has no unused ticket, the loop moves it from stack to path.
The first airport that runs out of tickets is the last stop of the itinerary. The reason is a count. Every airport except the start and the end has as many tickets out as in. Each time the walk enters such an airport, it uses one ticket in, so one ticket out is still left. The walk can only get stuck at the end airport.
The walk may leave some tickets unused. Those tickets form loops that start and end at an airport already on stack. When the loop backs up to such an airport, it walks the loop, and the loop is placed in the right spot, because its airports reach path before the airports under them.
Example: for tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]], the smallest-first walk goes JFK -> KUL and gets stuck, with the loop JFK -> NRT -> JFK still unused. The correct itinerary is ["JFK", "NRT", "JFK", "KUL"].
One trace: ten tickets, one dead end, two loops
The board uses 10 tickets and 8 airports. The airport JFK is the start, because it has one more ticket out than in. The airport KUL is a dead end with no ticket out. The tickets are JFK -> ATL, ATL -> ORD, ORD -> JFK, JFK -> KUL, JFK -> NRT, NRT -> SFO, SFO -> ICN, ICN -> NRT, NRT -> LAX and LAX -> JFK.
The walk goes JFK, ATL, ORD, JFK. At JFK the smallest unused ticket goes to KUL, so the walk goes there and gets stuck. KUL moves to path. This is the first dead end, and KUL is the last stop.
The loop backs up to JFK, which still has a ticket to NRT. The walk goes NRT, LAX, JFK and gets stuck again, because JFK has no ticket left. JFK and LAX move to path. At NRT, the ticket to SFO is still unused. The walk goes SFO, ICN, NRT, and then everything moves to path in turn.
The final path is [KUL, JFK, LAX, NRT, ICN, SFO, NRT, JFK, ORD, ATL, JFK]. Reversed, it is [JFK, ATL, ORD, JFK, NRT, SFO, ICN, NRT, LAX, JFK, KUL]. The board uses 10 steps that delete a ticket and 11 steps that move an airport to path.
The traps: writing on arrival, the start, the sort and the reversal
Do not write an airport into the answer when you first reach it. On the board tickets, the greedy walk goes JFK, ATL, ORD, JFK, KUL and stops, because it is stuck at KUL. It used 4 of the 10 tickets. The blueprint writes an airport only when its tickets are used up, so the loops are not lost.
The start must be the airport with balance[x] == 1. For edges = [[1, 0], [0, 2]], the correct walk is [1, 0, 2]. Starting at the smallest node, 0, gives [0, 2] and leaves the ticket 1 -> 0 unused. Only when every airport is balanced is the path a circuit, and then it starts at min(graph).
The tickets are sorted with reverse=True, so pop() takes the smallest neighbour in O(1). With an ascending sort, pop() takes the largest. On the board tickets, the ascending sort gives [JFK, NRT, SFO, ICN, NRT, LAX, JFK, ATL, ORD, JFK, KUL]. This is a valid walk, but the correct answer goes JFK, ATL and not JFK, NRT.
The last line is path[::-1]. Airports reach path last-first. Without the reversal, the example [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] returns [SJC, SFO, LHR, MUC, JFK] and not [JFK, MUC, LHR, SFO, SJC].
The cost, and the neighbours
Sorting the tickets costs O(E log E). The walk then deletes each ticket once and moves each airport to path once, which is O(E). The total is O(E log E) time. graph, balance, stack and path hold O(E) entries, so the space is O(E).
On the board, 10 tickets give 11 airports in the answer. Each ticket is deleted in one step, and each of the 11 stops reaches path in one step.
The same walk solves Valid Arrangement of Pairs (LC 2097), where the pairs are the edges and any valid order is accepted. Cracking the Safe (LC 753) uses it on a graph whose nodes are strings, and the walk gives the shortest string that contains every combination.
The Topological Sort card solves a different question. In Course Schedule II (LC 210), every node appears once, after everything it depends on. That is an order of the nodes. Here every edge is used once, and a node can appear many times. If you only need to know which nodes are joined, a plain search is enough, as in Number of Provinces (LC 547).
60-Second Pitch
"Every ticket must be used once, so this is an Eulerian path, and I use Hierholzer's algorithm. I sort the tickets in reverse and keep them in a list for each airport, so pop() takes the smallest destination. I start at the airport with one more ticket out than in, or at the smallest airport if all are balanced. I keep a stack. If the top airport has an unused ticket, I delete it and push the destination. If it has none, I move the airport to path. An airport goes into path only when its tickets are used up. So a dead end is placed last, and a loop that the walk skipped is walked when the stack backs up to its airport. At the end I return path reversed. Sorting costs O(E log E), and the walk costs O(E). The space is O(E)."
Common Questions
- Why does the walk get stuck only at the end airport?
Every airport except the start and the end has as many tickets out as in. Each entry into such an airport uses one ticket in, so one ticket out is still unused. The start has one extra ticket out. So the only airport where the walk can run out of tickets is the end.
- Why do you add an airport to
pathwhen it is stuck, and not when it is reached? The first stuck airport is the last stop. A loop that the walk skipped starts and ends at an airport that is still on
stack. If airports were written on arrival, the dead end would be written before the loop, and the loop would be lost. With the stuck rule, the loop is walked and placed before the airports under it.- How do you get the smallest itinerary?
Sort the tickets in reverse and use
pop(), so each airport always takes its smallest unused destination first. Hierholzer's algorithm with this rule returns the smallest valid walk for Reconstruct Itinerary (LC 332).- What are the time and space complexity?
O(E log E) time, because of the sort, and O(E) space. The walk itself deletes each ticket once and moves each airport to
pathonce.- How do you know that a valid walk exists?
Check the counts. In a directed graph, an Eulerian path needs every airport balanced, except at most one with one more ticket out than in (the start) and one with one more ticket in than out (the end). The edges must also be joined in one piece. Reconstruct Itinerary (LC 332) promises that a valid itinerary exists.
SWE Reasoning
Spot it
- Every ticket, domino, pair or transition must be used exactly once in one walk.
- The question asks for the walk or the order of the stops, and not only whether it exists.
- The wording says itinerary, arrangement, or the shortest string that contains every combination.
- When two choices are possible, the smallest one must win, so the neighbours are sorted.
- Trying every order of the edges would take O(E!) time, which is far too slow.
The invariant, step by step
- The tickets are sorted in reverse order, so
graph[u].pop()takes the smallest neighbour ofu. startis the airport withbalance[x] == 1. If every airport is balanced,startis the smallest airport.- The loop looks at
node = stack[-1]. Ifgraph[node]is not empty, it deletes the smallest ticket withpop()and pushes the airport it leads to. - If
graph[node]is empty, the loop movesnodefromstacktopath. No edge leaves this airport any more, so it is final in the rest of the walk. stackis always a walk fromstartover used tickets, andpathholds the final part of the answer, last-first.- When
stackis empty, every ticket was used.path[::-1]is the itinerary.
Traps
- Writing an airport into the answer when it is first reached. The walk can enter the final dead end before a loop is used, and the loop is lost. Add an airport to
pathonly when its tickets run out. - Starting at the smallest airport. A walk that is not a circuit must start at the airport with
balance[x] == 1. - Sorting ascending. Then
pop()takes the largest neighbour, and the walk is not the smallest one. Sort withreverse=True. - Using
pop(0)for the smallest neighbour. It moves every other item, so each step costs O(E). Sort in reverse and usepop(). - Returning
pathwithout reversing it. Airports reachpathlast-first. Returnpath[::-1].