What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 201 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

16. Eulerian Path (Hierholzer's): Reconstruct Itinerary (LC 332) • Invariant Proof & Speed-Run

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

You will see how Hierholzer's algorithm rebuilds a trip that uses every ticket exactly once.

Target Frequency:GoogleAmazonMeta

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.

Worked Examples

Example 1

Input:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output:["JFK","MUC","LHR","SFO","SJC"]

Explanation: Only one order uses every ticket: JFK -> MUC -> LHR -> SFO -> SJC.

Example 2

Input:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output:["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation: JFK -> SFO -> ATL -> JFK -> ATL -> SFO also uses every ticket, but at the second airport ATL comes before SFO, so the answer starts JFK, ATL.

⚖️Formal Constraints & Bounds

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Every ticket is an edge to use exactly once, so the trip is an Eulerian path from JFK. Follow the smallest unused ticket and delete it, write an airport down only when it has no ticket left, and reverse at the end: a dead end reached too early is written down first and so lands last.

Real-World Scenario & Production Applications

Rebuilding a route from unordered legs (flight coupons, delivery hops, log records of moves), and genome assembly, where overlapping fragments are joined by walking every overlap exactly once.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Store the Tickets Smallest-Last

Sort the tickets in reverse and append each destination to graph[src], so pop() from the end always gives the smallest unused airport.

Mathematical Recurrence / Code Invariant

graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
    graph[src].append(dst)

Step-by-Step Execution Trace Table

Step-by-Step Hierholzer (tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]])

Step 1 (Store the Tickets): sorted in reverse, graph = {"NRT": ["JFK"], "JFK": ["NRT", "KUL"]}: each list ends with its smallest airport.
Step 2 (Follow the Smallest): stack = ["JFK"]; JFK still has tickets, pop "KUL": stack = ["JFK", "KUL"].
Step 3 (A Dead End): KUL has no ticket, so it is final: path = ["KUL"], stack = ["JFK"]. JFK still has a ticket, so KUL can't be the trip's second stop: it goes to the end.
Step 4 (The Loop): JFK -> NRT, then NRT -> JFK: stack = ["JFK", "NRT", "JFK"], and every ticket is used.
Step 5 (Unwind): JFK, NRT and JFK run out of tickets in turn: path = ["KUL", "JFK", "NRT", "JFK"].
Step 6 (Reverse): path[::-1] = ["JFK", "NRT", "JFK", "KUL"] ✅.

Full Walkthrough6 Steps

Input:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]Expected:["JFK","MUC","LHR","SFO","SJC"]

1⚡ STEP(Store the Tickets)

sorted in reverse, graph = {"NRT": ["JFK"], "JFK": ["NRT", "KUL"]}: each list ends with its smallest airport.

2⚡ FIFO DRAIN(Follow the Smallest)

stack = ["JFK"]; JFK still has tickets, pop "KUL": stack = ["JFK", "KUL"].

3✂️ PRUNED(A Dead End)

path = ["KUL"]

KUL has no ticket, so it is final: path = ["KUL"], stack = ["JFK"]. JFK still has a ticket, so KUL can't be the trip's second stop: it goes to the end.

4⚡ STEP(The Loop)

JFK -> NRT, then NRT -> JFK: stack = ["JFK", "NRT", "JFK"], and every ticket is used.

5⚡ STEP(Unwind)

path = ["KUL", "JFK", "NRT", "JFK"]

JFK, NRT and JFK run out of tickets in turn: path = ["KUL", "JFK", "NRT", "JFK"].

6✅ RECORD / GOAL(Reverse)

path[::-1] = ["JFK", "NRT", "JFK", "KUL"] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	graph: each airport's unused tickets, stored so the smallest comes out first
2	stack = [start]; path = []
3	while stack:
4	# either follow a ticket out of the top airport, or move a finished airport
5	return ... # the finished airports, in trip order

Target: Reconstruct Itinerary (LeetCode 332). Sorted in reverse, each list ends with its smallest airport, so pop() takes it in O(1)

Boundary Model: Graph Component Traversal & Visited State Machine

Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.

Loop Invariant Termination

Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A walk that uses every edge of a graph exactly once is an Eulerian path. Hierholzer's algorithm builds it in one pass: walk from the start, deleting each edge as you follow it, and when you reach a node with no edge left, that node is final, so move it into the answer. Backing up along the walk, any node that still has edges starts a detour, and the detour is finished before the node itself. Reversing the finished nodes gives the path. Reconstruct Itinerary is this walk over the tickets, starting at JFK, with the smallest airport taken first.

🧳 The Analogy: Rolling Up a Road Trip Backwards

Imagine driving a road trip where every road must be used once, taking the alphabetically first road each time. When you reach a town with no unused road, that town must be where the trip ends, or at least where this part of it ends, so you write it at the bottom of your log. Then you back up: the first town you back into that still has an unused road sends you on a side loop, and that loop is logged, bottom up, before the town itself. Read the log from the bottom to the top and you have the whole trip in order.

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

while stack:
    node = stack[-1]
    if graph[node]:
        stack.append(graph[node].pop())   # take a road and burn it
    else:
        path.append(stack.pop())          # dead end: this town is final
return path[::-1]

The trick is when a node is written down. Writing it when you first reach it fails as soon as the smallest road leads to the final dead end too early: with tickets JFK -> KUL, JFK -> NRT and NRT -> JFK, the smallest road reaches KUL while the loop through NRT is still unused. Writing it when it runs out of roads puts KUL last, where it belongs.

💡 Summary

Hierholzer's algorithm follows unused edges, deletes each as it goes, and writes a node down only when it is out of edges; reversing that list gives an Eulerian path in O(E) steps after the edges are stored.

🧠 Variable Roles & Pattern Refresher:

graph[a]: the unused tickets out of airport a, smallest last so pop() takes it.
stack: the walk from JFK over tickets used so far.
node: the airport on top of the walk.
path: airports that are finished, in reverse trip order.

Writing a node down when first reached: add node to path when it is popped from stack with no edge left, not when it is first reached: the walk can enter the final dead end before a cycle has been used, and only this order puts the cycle back in its place.
Starting anywhere: start at the node with balance[x] == 1, one more edge out than in; start at any node with edges only when every node is balanced, because then the path is a circuit.
Unsorted or pop(0): sorted(edges, reverse=True) lets pop() take the smallest neighbour in O(1), which gives the smallest walk that Reconstruct Itinerary (LC 332) asks for; pop(0) on a list would cost O(E) per step. When any valid walk will do, as in Valid Arrangement of Pairs (LC 2097), skip the sort and the run is O(E).
Forgetting to reverse: return path[::-1]: nodes are finished last-first, so the unreversed list is the walk backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an every-edge-once walk and defends Hierholzer's post-order.

Pattern Recognition Signals

The 10-second spot

The trip "uses every ticket in tickets exactly once" and "begins at "JFK"": every edge used once in one walk is an Eulerian path. "The one whose list of airports comes first" adds only an order on the choices, so Hierholzer's algorithm with the smallest ticket first.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Every ticket is followed at most once and deleted when it is (graph[node].pop()); stack is a walk from JFK over used tickets; an airport moves into path only when graph[node] is empty, so path holds, last-first, the part of the trip that is already final.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

path.append(stack.pop()) only when graph[node] is empty: writing an airport down when first reached fails on JFK -> KUL, JFK -> NRT, NRT -> JFK, where the smallest ticket reaches the dead end KUL before the NRT loop is used.
sorted(tickets, reverse=True) with pop() from the end: unsorted lists give some trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.
Airports with no outgoing ticket (like KUL) are still read with graph[node]: a defaultdict(list) answers with an empty list instead of a missing key.

The 60-Second Interview Pitch

Say this out loud before you type a single line

Every ticket has to be used exactly once, so this is an Eulerian path, and I'd build it with Hierholzer's algorithm. I store each airport's destinations in reverse sorted order, so popping from the end gives the smallest one. Then I keep a stack for the walk, starting at JFK. If the airport on top still has a ticket, I pop it and push the destination, which uses the ticket up. If it has none, that airport is final, so I move it from the stack into the answer. The key is when an airport is written down: only when it runs out of tickets. If I wrote airports down on arrival, the smallest ticket could lead into the final dead end while a loop is still unused. At the end I reverse the list, since airports finish last-first. It's O(E log E) time for the sort and O(E) space.

So: tickets sorted in reverse, stack = ["JFK"], pop a ticket or move a finished airport into path, return path[::-1].

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(E log E)

Look at the code: sorted(tickets, reverse=True) costs O(E log E) comparisons of short strings, and appending each ticket to graph is O(E). In the while stack loop, every step either pops a ticket from graph[node] and pushes it on stack (E times in all, since a popped ticket is gone) or moves an airport from stack to path (once per push, E + 1 times). Each step is O(1), so the walk is O(E). Reversing path is O(E). Total: O(E log E).

SPACE COMPLEXITY

O(E)

graph holds the E tickets, stack and path at most E + 1 airports each. There is no recursion, so the call stack is O(1). The output list is the E + 1 airports of path reversed.

Formal Recurrence Relation

T(E) = E log E (sort) + 2E + 1 (walk) + E (reverse) = O(E log E)

Derivation Progression

Store the tickets

sorted(tickets, reverse=True): O(E log E); E appends

The sort puts each airport's smallest destination last in its list.

The walk

E pops from graph + (E + 1) moves into path: O(E)

Every ticket is used once and deleted; every airport pushed on stack is later moved to path once.

Reverse

path[::-1]: O(E)

The finished airports are in reverse trip order.

Variable Definitions

$E$

Number of tickets, len(tickets); the trip visits E + 1 airports

$V$

Number of distinct airports, at most E + 1

Memory Architecture & Bounds

🟣 Call Stack

O(1): an explicit stack, no recursion

🔵 Auxiliary Heap

O(E): graph holds every ticket; stack and path at most E + 1 airports

🟢 Output Space

O(E): the E + 1 airports of the trip

Boundary Best / Worst Cases

Best Case

$O(E log E)$ : the sort runs on every input.

Average Case

$O(E log E)$ .

Worst Case

$O(E log E)$ .

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: **"uses every ticket in tickets exactly once"**, **"begins at "JFK""**. Every edge used once in one walk is an Eulerian path; a tie rule on the order only decides which edge to take first, so a Senior SWE reaches for Hierholzer's algorithm with the smallest ticket first, not backtracking.

CONSTRAINTS & BOUNDS

$E \le 300$ tickets, so at most 301 airports on the trip. Budget: $O(E \log E)$ for the sort and $O(E)$ for the walk; backtracking also passes at this size, but its worst case grows exponentially with the number of dead ends.

FAANG PRODUCTION TRAPS & EDGE CASES

Writing an airport down on arrival instead of on exhaustion. At scale, a recursive version can pass the recursion limit on long trips (hundreds of thousands of edges); the explicit stack here doesn't.

Core Algorithmic State Invariants

1. Each Ticket Is Used Once

graph[a] holds the unused tickets out of airport a, sorted so the smallest is last; stack.append(graph[node].pop()) both picks the ticket and deletes it.

2. An Airport Is Final When It Runs Out of Tickets

path.append(stack.pop()) runs only when graph[node] is empty. A dead end reached too early is written down first, and any loop still hanging off an earlier airport is walked and written before that airport.

3. Reverse at the End

Airports finish last-first, so path[::-1] is the trip from JFK. Sorting costs O(E log E); the walk pushes and pops each ticket once, O(E); space O(E).

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

You will see how Hierholzer's algorithm rebuilds a trip that uses every ticket exactly once.

Target Frequency:GoogleAmazonMeta

Worked Examples

Example 1

Input:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output:["JFK","MUC","LHR","SFO","SJC"]

Explanation: Only one order uses every ticket: JFK -> MUC -> LHR -> SFO -> SJC.

Example 2

Input:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output:["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation: JFK -> SFO -> ATL -> JFK -> ATL -> SFO also uses every ticket, but at the second airport ATL comes before SFO, so the answer starts JFK, ATL.

⚖️Formal Constraints & Bounds

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi and toi consist of uppercase English letters.
fromi != toi

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Rebuilding a route from unordered legs (flight coupons, delivery hops, log records of moves), and genome assembly, where overlapping fragments are joined by walking every overlap exactly once.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Store the Tickets Smallest-Last

Sort the tickets in reverse and append each destination to graph[src], so pop() from the end always gives the smallest unused airport.

Mathematical Recurrence / Code Invariant

graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
    graph[src].append(dst)

Step-by-Step Execution Trace Table

Step-by-Step Hierholzer (tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]])

Step 1 (Store the Tickets): sorted in reverse, graph = {"NRT": ["JFK"], "JFK": ["NRT", "KUL"]}: each list ends with its smallest airport.
Step 2 (Follow the Smallest): stack = ["JFK"]; JFK still has tickets, pop "KUL": stack = ["JFK", "KUL"].
Step 3 (A Dead End): KUL has no ticket, so it is final: path = ["KUL"], stack = ["JFK"]. JFK still has a ticket, so KUL can't be the trip's second stop: it goes to the end.
Step 4 (The Loop): JFK -> NRT, then NRT -> JFK: stack = ["JFK", "NRT", "JFK"], and every ticket is used.
Step 5 (Unwind): JFK, NRT and JFK run out of tickets in turn: path = ["KUL", "JFK", "NRT", "JFK"].
Step 6 (Reverse): path[::-1] = ["JFK", "NRT", "JFK", "KUL"] ✅.

Full Walkthrough6 Steps

Input:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]Expected:["JFK","MUC","LHR","SFO","SJC"]

1⚡ STEP(Store the Tickets)

sorted in reverse, graph = {"NRT": ["JFK"], "JFK": ["NRT", "KUL"]}: each list ends with its smallest airport.

2⚡ FIFO DRAIN(Follow the Smallest)

stack = ["JFK"]; JFK still has tickets, pop "KUL": stack = ["JFK", "KUL"].

3✂️ PRUNED(A Dead End)

path = ["KUL"]

KUL has no ticket, so it is final: path = ["KUL"], stack = ["JFK"]. JFK still has a ticket, so KUL can't be the trip's second stop: it goes to the end.

4⚡ STEP(The Loop)

JFK -> NRT, then NRT -> JFK: stack = ["JFK", "NRT", "JFK"], and every ticket is used.

5⚡ STEP(Unwind)

path = ["KUL", "JFK", "NRT", "JFK"]

JFK, NRT and JFK run out of tickets in turn: path = ["KUL", "JFK", "NRT", "JFK"].

6✅ RECORD / GOAL(Reverse)

path[::-1] = ["JFK", "NRT", "JFK", "KUL"] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	graph: each airport's unused tickets, stored so the smallest comes out first
2	stack = [start]; path = []
3	while stack:
4	# either follow a ticket out of the top airport, or move a finished airport
5	return ... # the finished airports, in trip order

Target: Reconstruct Itinerary (LeetCode 332). Sorted in reverse, each list ends with its smallest airport, so pop() takes it in O(1)

Boundary Model: Graph Component Traversal & Visited State Machine

Maintains visited set or 3-color states (WHITE=unvisited, GREY=visiting/cycle, BLACK=processed) across adjacency lists.

Loop Invariant Termination

Loop outer vertices 0..V-1 to handle disconnected subgraphs; explore edges via BFS/DFS/PriorityQueue.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧳 The Analogy: Rolling Up a Road Trip Backwards

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

while stack:
    node = stack[-1]
    if graph[node]:
        stack.append(graph[node].pop())   # take a road and burn it
    else:
        path.append(stack.pop())          # dead end: this town is final
return path[::-1]

💡 Summary

🧠 Variable Roles & Pattern Refresher:

graph[a]: the unused tickets out of airport a, smallest last so pop() takes it.
stack: the walk from JFK over tickets used so far.
node: the airport on top of the walk.
path: airports that are finished, in reverse trip order.

Writing a node down when first reached: add node to path when it is popped from stack with no edge left, not when it is first reached: the walk can enter the final dead end before a cycle has been used, and only this order puts the cycle back in its place.
Starting anywhere: start at the node with balance[x] == 1, one more edge out than in; start at any node with edges only when every node is balanced, because then the path is a circuit.
Unsorted or pop(0): sorted(edges, reverse=True) lets pop() take the smallest neighbour in O(1), which gives the smallest walk that Reconstruct Itinerary (LC 332) asks for; pop(0) on a list would cost O(E) per step. When any valid walk will do, as in Valid Arrangement of Pairs (LC 2097), skip the sort and the run is O(E).
Forgetting to reverse: return path[::-1]: nodes are finished last-first, so the unreversed list is the walk backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an every-edge-once walk and defends Hierholzer's post-order.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

path.append(stack.pop()) only when graph[node] is empty: writing an airport down when first reached fails on JFK -> KUL, JFK -> NRT, NRT -> JFK, where the smallest ticket reaches the dead end KUL before the NRT loop is used.
sorted(tickets, reverse=True) with pop() from the end: unsorted lists give some trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.
Airports with no outgoing ticket (like KUL) are still read with graph[node]: a defaultdict(list) answers with an empty list instead of a missing key.

The 60-Second Interview Pitch

Say this out loud before you type a single line

Every ticket has to be used exactly once, so this is an Eulerian path, and I'd build it with Hierholzer's algorithm. I store each airport's destinations in reverse sorted order, so popping from the end gives the smallest one. Then I keep a stack for the walk, starting at JFK. If the airport on top still has a ticket, I pop it and push the destination, which uses the ticket up. If it has none, that airport is final, so I move it from the stack into the answer. The key is when an airport is written down: only when it runs out of tickets. If I wrote airports down on arrival, the smallest ticket could lead into the final dead end while a loop is still unused. At the end I reverse the list, since airports finish last-first. It's O(E log E) time for the sort and O(E) space.

So: tickets sorted in reverse, stack = ["JFK"], pop a ticket or move a finished airport into path, return path[::-1].

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(E log E)

SPACE COMPLEXITY

O(E)

graph holds the E tickets, stack and path at most E + 1 airports each. There is no recursion, so the call stack is O(1). The output list is the E + 1 airports of path reversed.

Formal Recurrence Relation

T(E) = E log E (sort) + 2E + 1 (walk) + E (reverse) = O(E log E)

Derivation Progression

Store the tickets

sorted(tickets, reverse=True): O(E log E); E appends

The sort puts each airport's smallest destination last in its list.

The walk

E pops from graph + (E + 1) moves into path: O(E)

Every ticket is used once and deleted; every airport pushed on stack is later moved to path once.

Reverse

path[::-1]: O(E)

The finished airports are in reverse trip order.

Variable Definitions

$E$

Number of tickets, len(tickets); the trip visits E + 1 airports

$V$

Number of distinct airports, at most E + 1

Memory Architecture & Bounds

🟣 Call Stack

O(1): an explicit stack, no recursion

🔵 Auxiliary Heap

O(E): graph holds every ticket; stack and path at most E + 1 airports

🟢 Output Space

O(E): the E + 1 airports of the trip

Boundary Best / Worst Cases

Best Case

$O(E log E)$ : the sort runs on every input.

Average Case

$O(E log E)$ .

Worst Case

$O(E log E)$ .

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Each Ticket Is Used Once

graph[a] holds the unused tickets out of airport a, sorted so the smallest is last; stack.append(graph[node].pop()) both picks the ticket and deletes it.

2. An Airport Is Final When It Runs Out of Tickets

3. Reverse at the End

Airports finish last-first, so path[::-1] is the trip from JFK. Sorting costs O(E log E); the walk pushes and pops each ticket once, O(E); space O(E).

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: RECONSTRUCT ITINERARY (LEETCODE 332)

T = O(E log E)S = O(E)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Store the edges so the smallest neighbour comes out first	`graph = defaultdict(list) for src, dst in sorted(tickets, reverse=True): graph[src].append(dst)`	Sorted in reverse, each list ends with its smallest airport, so pop() takes it in O(1)
Start where the path must start	`path, stack = [], ["JFK"]`	The problem fixes the start; in general it is the node with one more edge out than in
Follow an unused edge and delete it	`node = stack[-1] if graph[node]: stack.append(graph[node].pop())`	pop() both chooses the ticket and removes it, so no ticket is used twice
A node with no edge left is final	`path.append(stack.pop())`	The trap line: a node joins the answer only when it runs out of edges, never when first reached
Reverse the finished nodes	`return path[::-1]`	Nodes are finished last-first, so the reversed list is the trip from JFK

while stack: node = stack[-1] if graph[node]: stack.append(graph[node].pop()) # take a road and burn it else: path.append(stack.pop()) # dead end: this town is final return path[::-1]

Canonical Invariant

Concrete Code

Engineering Rationale

Store the edges so the smallest neighbour comes out first

graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)

Sorted in reverse, each list ends with its smallest airport, so pop() takes it in O(1)

Start where the path must start

path, stack = [], ["JFK"]

The problem fixes the start; in general it is the node with one more edge out than in

Follow an unused edge and delete it

node = stack[-1]
if graph[node]:
stack.append(graph[node].pop())

pop() both chooses the ticket and removes it, so no ticket is used twice

A node with no edge left is final

path.append(stack.pop())

The trap line: a node joins the answer only when it runs out of edges, never when first reached

Reverse the finished nodes

return path[::-1]

Nodes are finished last-first, so the reversed list is the trip from JFK