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

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

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 uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

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

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

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

Core Insight

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"] ✅.

Code Shape

Archetype Code Shape

Python

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

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.

🔑 The Key Idea in the Code

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.

Writing an airport down when first reached: add it to path only when graph[node] is empty. With JFK -> KUL, JFK -> NRT, NRT -> JFK, the smallest ticket reaches the dead end KUL before the NRT loop is used, and writing airports on arrival puts KUL too early.
A dict without a default: an airport with no ticket out (like KUL) is still read with graph[node]; defaultdict(list) answers with an empty list, while a plain dict raises KeyError.
Unsorted or pop(0): sorted(tickets, reverse=True) lets pop() take the smallest destination in O(1). Unsorted lists give some valid trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
Forgetting to reverse: return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

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

This problem's traps are in Common Pitfalls above.

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.

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

Scale signal: backtracking over ticket orders can grow exponentially with the number of dead ends; Hierholzer's walk touches each ticket once after one $O(E \log E)$ sort.

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.

FAANG PRODUCTION TRAPS & EDGE CASES

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

Example 1 Is One Straight Line

Every airport has one ticket out, so the stack walks JFK -> MUC -> LHR -> SFO -> SJC. SJC runs out first, then each airport in turn moves into path, last-first; reversed, that is the trip.

Example 2 Takes the Smaller Ticket First

At JFK, ATL comes before SFO, so the walk goes JFK -> ATL -> JFK -> SFO -> ATL -> SFO and uses all five tickets without hitting a dead end early.

A Quick Self-Check

Every ticket is used once, so the answer always holds len(tickets) + 1 airports: 5 in Example 1 and 6 in Example 2.

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

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

Core Insight

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"] ✅.

Code Shape

Archetype Code Shape

Python

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

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧳 The Analogy: Rolling Up a Road Trip Backwards

🔑 The Key Idea in the Code

Writing an airport down when first reached: add it to path only when graph[node] is empty. With JFK -> KUL, JFK -> NRT, NRT -> JFK, the smallest ticket reaches the dead end KUL before the NRT loop is used, and writing airports on arrival puts KUL too early.
A dict without a default: an airport with no ticket out (like KUL) is still read with graph[node]; defaultdict(list) answers with an empty list, while a plain dict raises KeyError.
Unsorted or pop(0): sorted(tickets, reverse=True) lets pop() take the smallest destination in O(1). Unsorted lists give some valid trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
Forgetting to reverse: return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

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

This problem's traps are in Common Pitfalls above.

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.

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

Scale signal: backtracking over ticket orders can grow exponentially with the number of dead ends; Hierholzer's walk touches each ticket once after one $O(E \log E)$ sort.

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.

FAANG PRODUCTION TRAPS & EDGE CASES

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

Example 1 Is One Straight Line

Every airport has one ticket out, so the stack walks JFK -> MUC -> LHR -> SFO -> SJC. SJC runs out first, then each airport in turn moves into path, last-first; reversed, that is the trip.

Example 2 Takes the Smaller Ticket First

At JFK, ATL comes before SFO, so the walk goes JFK -> ATL -> JFK -> SFO -> ATL -> SFO and uses all five tickets without hitting a dead end early.

A Quick Self-Check

Every ticket is used once, so the answer always holds len(tickets) + 1 airports: 5 in Example 1 and 6 in Example 2.

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

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

Core Insight

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"] ✅.

Code Shape

Archetype Code Shape

Python

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

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧳 The Analogy: Rolling Up a Road Trip Backwards

🔑 The Key Idea in the Code

Writing an airport down when first reached: add it to path only when graph[node] is empty. With JFK -> KUL, JFK -> NRT, NRT -> JFK, the smallest ticket reaches the dead end KUL before the NRT loop is used, and writing airports on arrival puts KUL too early.
A dict without a default: an airport with no ticket out (like KUL) is still read with graph[node]; defaultdict(list) answers with an empty list, while a plain dict raises KeyError.
Unsorted or pop(0): sorted(tickets, reverse=True) lets pop() take the smallest destination in O(1). Unsorted lists give some valid trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
Forgetting to reverse: return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

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

This problem's traps are in Common Pitfalls above.

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.

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

Scale signal: backtracking over ticket orders can grow exponentially with the number of dead ends; Hierholzer's walk touches each ticket once after one $O(E \log E)$ sort.

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.

FAANG PRODUCTION TRAPS & EDGE CASES

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

Example 1 Is One Straight Line

Every airport has one ticket out, so the stack walks JFK -> MUC -> LHR -> SFO -> SJC. SJC runs out first, then each airport in turn moves into path, last-first; reversed, that is the trip.

Example 2 Takes the Smaller Ticket First

At JFK, ATL comes before SFO, so the walk goes JFK -> ATL -> JFK -> SFO -> ATL -> SFO and uses all five tickets without hitting a dead end early.

A Quick Self-Check

Every ticket is used once, so the answer always holds len(tickets) + 1 airports: 5 in Example 1 and 6 in Example 2.

Theory Context•Graph Algorithms

HardLC 332

Reconstruct Itinerary (LeetCode 332)

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

Core Insight

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"] ✅.

Code Shape

Archetype Code Shape

Python

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

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🧳 The Analogy: Rolling Up a Road Trip Backwards

🔑 The Key Idea in the Code

Writing an airport down when first reached: add it to path only when graph[node] is empty. With JFK -> KUL, JFK -> NRT, NRT -> JFK, the smallest ticket reaches the dead end KUL before the NRT loop is used, and writing airports on arrival puts KUL too early.
A dict without a default: an airport with no ticket out (like KUL) is still read with graph[node]; defaultdict(list) answers with an empty list, while a plain dict raises KeyError.
Unsorted or pop(0): sorted(tickets, reverse=True) lets pop() take the smallest destination in O(1). Unsorted lists give some valid trip, not the smallest; pop(0) gives the smallest but costs O(E) per step.
Forgetting to reverse: return path[::-1]: airports finish last-first, so the unreversed list is the trip backwards.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

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

This problem's traps are in Common Pitfalls above.

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.

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

Scale signal: backtracking over ticket orders can grow exponentially with the number of dead ends; Hierholzer's walk touches each ticket once after one $O(E \log E)$ sort.

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.

FAANG PRODUCTION TRAPS & EDGE CASES

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

Example 1 Is One Straight Line

Every airport has one ticket out, so the stack walks JFK -> MUC -> LHR -> SFO -> SJC. SJC runs out first, then each airport in turn moves into path, last-first; reversed, that is the trip.

Example 2 Takes the Smaller Ticket First

At JFK, ATL comes before SFO, so the walk goes JFK -> ATL -> JFK -> SFO -> ATL -> SFO and uses all five tickets without hitting a dead end early.

A Quick Self-Check

Every ticket is used once, so the answer always holds len(tickets) + 1 airports: 5 in Example 1 and 6 in Example 2.