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

The entire core curriculum of 12 patterns and 187 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.

15. All-Pairs Shortest Path (Floyd-Warshall): Course Schedule IV (LC 1462) • Invariant Proof & Speed-Run

Theory Context•Graph Algorithms

MediumLC 1462

Course Schedule IV (LeetCode 1462)

You will see how one Floyd-Warshall table answers every prerequisite query with a single lookup.

Target Frequency:GoogleAmazon

You answer a list of yes/no questions about course order. Query [uj, vj] in queries asks whether course uj must be taken before course vj, and the answer is true exactly when a chain of pairs from prerequisites leads from uj to vj: [uj, x1], [x1, x2], ..., [xm, vj], where the single pair [uj, vj] is the shortest possible chain.

In prerequisites, a pair [ai, bi] means course ai comes before course bi. The courses are numbered 0 to numCourses - 1, and the pairs never form a cycle. Return the answers as a list of booleans, one per query, in the order of queries.

Worked Examples

Example 1

Input:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

Output:[false,true]

Explanation: Course 1 is taken first, so the query `[1, 0]` is true; no chain leads from course 0 to course 1, so `[0, 1]` is false.

Example 2

Input:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]

Output:[false,false]

Explanation: With no pairs at all, no course needs another one first.

Example 3

Input:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]

Output:[true,true]

Explanation: Course 1 comes directly before both course 0 and course 2, so both answers are true.

⚖️Formal Constraints & Bounds

2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= numCourses - 1
ai != bi
All the pairs [ai, bi] are unique.
The prerequisites graph has no cycles.
1 <= queries.length <= 10⁴
0 <= ui, vi <= numCourses - 1
ui != vi

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Every prerequisite pair is one step in dist, and Floyd-Warshall with for k in range(n) outermost fills the table for every pair, so each query is one lookup, dist[u][v] < float("inf"). The Topological Sort tab solves it another way, passing each course's set of earlier courses forward in Kahn's order; both are O(V^3) in the worst case.

Real-World Scenario & Production Applications

Dependency checks in build systems and package managers (does module A depend on module B, directly or through others?), and access-control rules that inherit through chains of groups.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Adjacency List & In-Degree Initialization

Construct directed graph from edge pairs and compute in-degree for every vertex: in_degree[v] = number of prerequisite dependencies.

Mathematical Recurrence / Code Invariant

adj = defaultdict(list)
in_degree = [0] * numCourses
for dest, src in prerequisites:
    adj[src].append(dest)
    in_degree[dest] += 1

Step-by-Step Execution Trace Table

Step-by-Step Floyd-Warshall (numCourses = 4, prerequisites = [[0,3],[3,2],[2,1]], queries = [[0,1],[1,0],[3,1]])

Step 1 (Direct Steps Only): dist[i][i] = 0, and dist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry is inf.
Step 2 (k = 0, k = 1): No pair gets shorter: no path goes into course 0, and no path leaves course 1.
Step 3 (k = 2): Pair (3, 1): dist[3][2] + dist[2][1] = 1 + 1 = 2 < inf, so dist[3][1] = 2.
Step 4 (k = 3): Pair (0, 1): dist[0][3] + dist[3][1] = 1 + 2 = 3 < inf, so dist[0][1] = 3. This uses dist[3][1], built at k = 2: that is why k is the outermost loop. Pair (0, 2): 1 + 1 = 2, so dist[0][2] = 2.
Step 5 (Answer the Queries): dist[0][1] = 3 is finite, dist[1][0] = inf, dist[3][1] = 2 is finite: return [true, false, true] ✅.

Full Walkthrough5 Steps

Input:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]Expected:[false,true]

1⚡ STEP(Direct Steps Only)

dist[i][i] = 0, and dist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry is inf.

2⚡ STEP(k = 0, k = 1)

No pair gets shorter: no path goes into course 0, and no path leaves course 1.

3⚡ STEP(k = 2)

Pair (3, 1): dist[3][2] + dist[2][1] = 1 + 1 = 2 < inf, so dist[3][1] = 2.

4⚡ STEP(k = 3)

Pair (0, 1): dist[0][3] + dist[3][1] = 1 + 2 = 3 < inf, so dist[0][1] = 3. This uses dist[3][1], built at k = 2: that is why k is the outermost loop. Pair (0, 2): 1 + 1 = 2, so dist[0][2] = 2.

5✅ RECORD / GOAL(Answer the Queries)

dist[0][1] = 3 is finite, dist[1][0] = inf, dist[3][1] = 2 is finite: return [true, false, true] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	dist = V x V table: 0 on the diagonal, 1 per prerequisite pair, inf elsewhere
2	for _ in range(n): # three nested loops: the stop and the pair (i, j)
3	for _ in range(n):
4	for _ in range(n):
5	# try going through the stop
6	return [... for u, v in queries]

Target: Course Schedule IV (LeetCode 1462). Before any stop is allowed, a course reaches only itself and its direct followers

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

Floyd-Warshall answers "how far is every node from every other node?" with one table, dist[i][j], and one idea: allow the nodes as stops one at a time. Before any stop is allowed, dist holds only the direct edges. When node k is allowed, every pair i, j checks whether going i -> k -> j is shorter, dist[i][k] + dist[k][j] < dist[i][j]. After the last k, every node may be a stop, so the table holds every shortest path. Course Schedule IV only asks yes or no: course u is a prerequisite of course v exactly when dist[u][v] is finite, with every prerequisite pair worth one step.

🧳 The Analogy: Opening Transfer Hubs One by One

Imagine an airline that opens its transfer hubs one at a time. With no hub open, you can only fly the direct routes. When hub k opens, you check every pair of cities: is flying through k shorter than the best route you had? Every route you already had uses only hubs that opened earlier, so "through k" means a best route to k plus a best route from k, both made of earlier hubs. When the last hub has opened, you know the best route between every pair of cities.

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

for k in range(n):            # allow course k as a stop
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

The loop order is the whole trick. k is outermost, so when stop k is tried, dist[i][k] and dist[k][j] already hold the shortest paths through stops 0..k - 1. Put k inside the i and j loops and a pair is finished before the paths it needs have been built: in the chain 0 -> 3 -> 2 -> 1, course 0 would never reach course 1. For a yes/no question the same three loops can also run on booleans, reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]): AND means "through k", and OR keeps a path already found.

💡 Summary

Three nested loops, k outermost, fill the whole distance table in $O(V^3)$ time and $O(V^2)$ space; after that, each query is a single lookup.

🧠 Variable Roles & Pattern Refresher:

dist[i][j]: the shortest path from i to j using only the stops allowed so far; inf means no such path yet.
k: the stop being allowed in this pass of the outer loop.
i, j: the pair that tries to go through k.
u, v: a prerequisite pair when the table is built, then a query pair when it is read.

k inside the loops: for k in range(n) must be the outermost loop: with k inside the i and j loops, dist[i][k] is read before the paths through the smaller stops were allowed, so some pairs keep a distance that is too long.
One-way roads: two-way roads, as in Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334), need both dist[u][v] and dist[v][u] set; otherwise half the distances stay infinite.
Reversed pairs: in Course Schedule IV (LC 1462) the pair [ai, bi] puts ai first, so set dist[u][v] = 1 for [u, v]; dist[v][u] would answer every query backwards.
Breaking the tie the wrong way: in Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334), a tie goes to the largest city number: scan the cities upward and replace the best on <=, not <.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an all-pairs question and defends the order of Floyd-Warshall's loops.

Pattern Recognition Signals

The 10-second spot

Every query asks about a pair, "whether course uj must be taken before course vj", and the answer is true when "a chain of pairs from prerequisites leads from uj to vj", with "one per query" to return. With at most 100 courses and up to 10^4 queries, working out every pair once is the natural fit: all-pairs reachability, which is Floyd-Warshall on a table where each prerequisite is one step.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Once the outer loop has finished with k, dist[i][j] is the shortest path from i to j whose stops all lie among courses 0..k; a pair goes through k when dist[i][k] + dist[k][j] < dist[i][j], and a query is true when dist[u][v] < float("inf").

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for k in range(n) outermost: with k inside the i and j loops, in the chain 0 -> 3 -> 2 -> 1 the pair (0, 1) is finished before dist[3][1] exists, and course 0 never reaches course 1.
dist[u][v] = 1, not dist[v][u] = 1: the pair [ai, bi] puts ai first, so the step runs from ai to bi.
return [dist[u][v] < float("inf") for u, v in queries]: only reachability matters, so any finite distance means true.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This asks about pairs of courses, so I'd use Floyd-Warshall on a distance table where every prerequisite pair is one step. I allow the courses as stops one at a time: for each stop k, every pair i, j checks whether going through k is shorter, and takes it if so. After stop k, each entry is the shortest path whose stops all lie in the courses up to k, because the best such path either skips k or is a best path to k plus a best path from k, and both are already in the table. The trap is the loop order: k has to be the outermost loop, or a pair is finished before the paths it needs exist. Then each query is one lookup: is the distance finite? It's O(V cubed) time for the table, O(1) per query, and O(V squared) space.

So: one step per prerequisite, for k in range(n) outermost, then dist[u][v] < float("inf") per query.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V^3 + Q)

Look at the code: building dist touches V^2 entries and each prerequisite once, O(V^2 + E). The loops for k, for i and for j each run V times, and the body is one addition, one comparison and at most one write, so the table costs exactly V^3 checks. The return reads one entry per query, O(Q) in all. Since E <= V^2, the build is inside the V^3 term, and the answer is O(V^3 + Q): with few courses and many queries the Q term is the larger one.

SPACE COMPLEXITY

O(V^2)

dist is a V x V table: O(V^2). The loops use three counters and no recursion. The output list of Q booleans is not counted as extra space.

Formal Recurrence Relation

T(V, E, Q) = V^2 + E (build) + V^3 (triple loop) + Q (lookups) = O(V^3 + Q)

Derivation Progression

Build the table

V^2 entries of inf, V zeros, E ones: O(V^2 + E)

Only direct steps are known before any stop is allowed.

Allow every stop

for k, for i, for j: V · V · V = V^3 checks

Each pair tries each stop once, with O(1) work: add, compare, maybe write.

Answer the queries

one lookup per query: O(Q)

The finished table answers any pair at once.

Variable Definitions

$V$

Number of courses, numCourses

$E$

Number of prerequisite pairs, len(prerequisites)

$Q$

Number of queries, len(queries)

Memory Architecture & Bounds

🟣 Call Stack

O(1): three nested loops, no recursion

🔵 Auxiliary Heap

O(V^2): the V x V table dist

🟢 Output Space

O(Q): one boolean per query, not counted as extra space

Boundary Best / Worst Cases

Best Case

$O(V^3 + Q)$ : the triple loop runs in full on every input, then one lookup per query.

Average Case

$O(V^3 + Q)$ .

Worst Case

$O(V^3 + Q)$ .

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: **"whether course ujmust be taken before coursevj"**, **"a chain of pairs from prerequisitesleads fromujtovj"**. Many pair questions on a small graph (at most 100 courses, up to $10^4$ queries): build the answer for every pair once with Floyd-Warshall, then read each query from the table.

CONSTRAINTS & BOUNDS

$V \le 100$ courses, $E \le V(V-1)/2 = 4950$ pairs, $Q \le 10^4$ queries. Budget: $V^3 = 10^6$ checks for the table and $Q$ lookups, against up to $Q \cdot (V + E) \approx 5 \times 10^7$ for a search per query. The $V \times V$ table is $10^4$ entries.

FAANG PRODUCTION TRAPS & EDGE CASES

The loop order: k outermost, or pairs are finished before the paths they need exist. At scale the $O(V^2)$ table is the limit: for tens of thousands of nodes, keep one bitset row per node and OR rows along a topological order, or answer queries with a search from each queried source instead.

Core Algorithmic State Invariants

1. One Step per Prerequisite

dist starts with 0 on the diagonal, 1 for every pair [u, v] (u before v) and inf elsewhere. A query is true exactly when dist[u][v] ends up finite.

2. Allow the Stops One at a Time

For each k, every pair checks dist[i][k] + dist[k][j] < dist[i][j]. Once k is done, dist[i][j] is the shortest path whose stops lie among courses 0..k: the best such path avoids k or joins a best path to k and a best path from k.

3. k Is the Outermost Loop

With k inside the i and j loops, a pair is finished before the paths it needs are built (in the chain 0 -> 3 -> 2 -> 1, course 0 never reaches 1). Time O(V^3) for the table plus O(1) per query; space O(V^2).

Theory Context•Graph Algorithms

MediumLC 1462

Course Schedule IV (LeetCode 1462)

You will see how one Floyd-Warshall table answers every prerequisite query with a single lookup.

Target Frequency:GoogleAmazon

Worked Examples

Example 1

Input:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

Output:[false,true]

Explanation: Course 1 is taken first, so the query `[1, 0]` is true; no chain leads from course 0 to course 1, so `[0, 1]` is false.

Example 2

Input:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]

Output:[false,false]

Explanation: With no pairs at all, no course needs another one first.

Example 3

Input:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]

Output:[true,true]

Explanation: Course 1 comes directly before both course 0 and course 2, so both answers are true.

⚖️Formal Constraints & Bounds

2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= numCourses - 1
ai != bi
All the pairs [ai, bi] are unique.
The prerequisites graph has no cycles.
1 <= queries.length <= 10⁴
0 <= ui, vi <= numCourses - 1
ui != vi

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Dependency checks in build systems and package managers (does module A depend on module B, directly or through others?), and access-control rules that inherit through chains of groups.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Adjacency List & In-Degree Initialization

Construct directed graph from edge pairs and compute in-degree for every vertex: in_degree[v] = number of prerequisite dependencies.

Mathematical Recurrence / Code Invariant

adj = defaultdict(list)
in_degree = [0] * numCourses
for dest, src in prerequisites:
    adj[src].append(dest)
    in_degree[dest] += 1

Step-by-Step Execution Trace Table

Step-by-Step Floyd-Warshall (numCourses = 4, prerequisites = [[0,3],[3,2],[2,1]], queries = [[0,1],[1,0],[3,1]])

Step 1 (Direct Steps Only): dist[i][i] = 0, and dist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry is inf.
Step 2 (k = 0, k = 1): No pair gets shorter: no path goes into course 0, and no path leaves course 1.
Step 3 (k = 2): Pair (3, 1): dist[3][2] + dist[2][1] = 1 + 1 = 2 < inf, so dist[3][1] = 2.
Step 4 (k = 3): Pair (0, 1): dist[0][3] + dist[3][1] = 1 + 2 = 3 < inf, so dist[0][1] = 3. This uses dist[3][1], built at k = 2: that is why k is the outermost loop. Pair (0, 2): 1 + 1 = 2, so dist[0][2] = 2.
Step 5 (Answer the Queries): dist[0][1] = 3 is finite, dist[1][0] = inf, dist[3][1] = 2 is finite: return [true, false, true] ✅.

Full Walkthrough5 Steps

Input:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]Expected:[false,true]

1⚡ STEP(Direct Steps Only)

dist[i][i] = 0, and dist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry is inf.

2⚡ STEP(k = 0, k = 1)

No pair gets shorter: no path goes into course 0, and no path leaves course 1.

3⚡ STEP(k = 2)

Pair (3, 1): dist[3][2] + dist[2][1] = 1 + 1 = 2 < inf, so dist[3][1] = 2.

4⚡ STEP(k = 3)

5✅ RECORD / GOAL(Answer the Queries)

dist[0][1] = 3 is finite, dist[1][0] = inf, dist[3][1] = 2 is finite: return [true, false, true] ✅.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	dist = V x V table: 0 on the diagonal, 1 per prerequisite pair, inf elsewhere
2	for _ in range(n): # three nested loops: the stop and the pair (i, j)
3	for _ in range(n):
4	for _ in range(n):
5	# try going through the stop
6	return [... for u, v in queries]

Target: Course Schedule IV (LeetCode 1462). Before any stop is allowed, a course reaches only itself and its direct followers

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: Opening Transfer Hubs One by One

🪄 Breaking Down the Code's "Magic Trick"

Code / Blueprint

for k in range(n):            # allow course k as a stop
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

💡 Summary

Three nested loops, k outermost, fill the whole distance table in $O(V^3)$ time and $O(V^2)$ space; after that, each query is a single lookup.

🧠 Variable Roles & Pattern Refresher:

dist[i][j]: the shortest path from i to j using only the stops allowed so far; inf means no such path yet.
k: the stop being allowed in this pass of the outer loop.
i, j: the pair that tries to go through k.
u, v: a prerequisite pair when the table is built, then a query pair when it is read.

k inside the loops: for k in range(n) must be the outermost loop: with k inside the i and j loops, dist[i][k] is read before the paths through the smaller stops were allowed, so some pairs keep a distance that is too long.
One-way roads: two-way roads, as in Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334), need both dist[u][v] and dist[v][u] set; otherwise half the distances stay infinite.
Reversed pairs: in Course Schedule IV (LC 1462) the pair [ai, bi] puts ai first, so set dist[u][v] = 1 for [u, v]; dist[v][u] would answer every query backwards.
Breaking the tie the wrong way: in Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334), a tie goes to the largest city number: scan the cities upward and replace the best on <=, not <.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer spots an all-pairs question and defends the order of Floyd-Warshall's loops.

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

for k in range(n) outermost: with k inside the i and j loops, in the chain 0 -> 3 -> 2 -> 1 the pair (0, 1) is finished before dist[3][1] exists, and course 0 never reaches course 1.
dist[u][v] = 1, not dist[v][u] = 1: the pair [ai, bi] puts ai first, so the step runs from ai to bi.
return [dist[u][v] < float("inf") for u, v in queries]: only reachability matters, so any finite distance means true.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This asks about pairs of courses, so I'd use Floyd-Warshall on a distance table where every prerequisite pair is one step. I allow the courses as stops one at a time: for each stop k, every pair i, j checks whether going through k is shorter, and takes it if so. After stop k, each entry is the shortest path whose stops all lie in the courses up to k, because the best such path either skips k or is a best path to k plus a best path from k, and both are already in the table. The trap is the loop order: k has to be the outermost loop, or a pair is finished before the paths it needs exist. Then each query is one lookup: is the distance finite? It's O(V cubed) time for the table, O(1) per query, and O(V squared) space.

So: one step per prerequisite, for k in range(n) outermost, then dist[u][v] < float("inf") per query.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V^3 + Q)

SPACE COMPLEXITY

O(V^2)

dist is a V x V table: O(V^2). The loops use three counters and no recursion. The output list of Q booleans is not counted as extra space.

Formal Recurrence Relation

T(V, E, Q) = V^2 + E (build) + V^3 (triple loop) + Q (lookups) = O(V^3 + Q)

Derivation Progression

Build the table

V^2 entries of inf, V zeros, E ones: O(V^2 + E)

Only direct steps are known before any stop is allowed.

Allow every stop

for k, for i, for j: V · V · V = V^3 checks

Each pair tries each stop once, with O(1) work: add, compare, maybe write.

Answer the queries

one lookup per query: O(Q)

The finished table answers any pair at once.

Variable Definitions

$V$

Number of courses, numCourses

$E$

Number of prerequisite pairs, len(prerequisites)

$Q$

Number of queries, len(queries)

Memory Architecture & Bounds

🟣 Call Stack

O(1): three nested loops, no recursion

🔵 Auxiliary Heap

O(V^2): the V x V table dist

🟢 Output Space

O(Q): one boolean per query, not counted as extra space

Boundary Best / Worst Cases

Best Case

$O(V^3 + Q)$ : the triple loop runs in full on every input, then one lookup per query.

Average Case

$O(V^3 + Q)$ .

Worst Case

$O(V^3 + Q)$ .

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. One Step per Prerequisite

dist starts with 0 on the diagonal, 1 for every pair [u, v] (u before v) and inf elsewhere. A query is true exactly when dist[u][v] ends up finite.

2. Allow the Stops One at a Time

3. k Is the Outermost Loop

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: COURSE SCHEDULE IV (LEETCODE 1462)

T = O(V^3 + Q)S = O(V^2)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Start with the direct edges only	`dist = [[float("inf")] * n for _ in range(n)] for i in range(n): dist[i][i] = 0`	Before any stop is allowed, a course reaches only itself and its direct followers
Each edge is one step	`for u, v in prerequisites: dist[u][v] = 1`	Only reachability matters here, so a weight of 1 turns 'is there a path?' into 'is dist finite?'
Allow the stops one at a time, outermost	`for k in range(n):`	The trap line: with k outermost, dist[i][k] and dist[k][j] already use every earlier stop when k is tried
Every pair tries the new stop	`for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]`	The best path with stops in 0..k either avoids k or is a best path to k plus a best path from k
Answer each query with one lookup	`return [dist[u][v] < float("inf") for u, v in queries]`	u is a prerequisite of v exactly when some path leads from u to v

for k in range(n): # allow course k as a stop for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]

Canonical Invariant

Concrete Code

Engineering Rationale

Start with the direct edges only

dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0

Before any stop is allowed, a course reaches only itself and its direct followers

Each edge is one step

for u, v in prerequisites:
dist[u][v] = 1

Only reachability matters here, so a weight of 1 turns 'is there a path?' into 'is dist finite?'

Allow the stops one at a time, outermost

for k in range(n):

The trap line: with k outermost, dist[i][k] and dist[k][j] already use every earlier stop when k is tried

Every pair tries the new stop

for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]

The best path with stops in 0..k either avoids k or is a best path to k plus a best path from k

Answer each query with one lookup

return [dist[u][v] < float("inf") for u, v in queries]

u is a prerequisite of v exactly when some path leads from u to v