Course Schedule IV (LeetCode 1462)
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
numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]][false,true][1, 0] is true; no chain leads from course 0 to course 1, so [0, 1] is false.numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]][false,false]numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]][true,true]⚖️Formal Constraints & Bounds
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != biAll the pairs
[ai, bi]are unique.The prerequisites graph has no cycles.
1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != vi
Core Insight
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
Fill a V x V table with inf, put 0 on the diagonal and 1 for every pair [u, v] (course u before course v).
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v in prerequisites:
dist[u][v] = 1Step-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, anddist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry isinf. - 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, sodist[3][1] = 2. - Step 4 (k = 3): Pair (0, 1):
dist[0][3] + dist[3][1] = 1 + 2 = 3 < inf, sodist[0][1] = 3. This usesdist[3][1], built atk = 2: that is whykis the outermost loop. Pair (0, 2):1 + 1 = 2, sodist[0][2] = 2. - Step 5 (Answer the Queries):
dist[0][1] = 3is finite,dist[1][0] = inf,dist[3][1] = 2is finite: return[true, false, true]✅.
numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]Expected:[false,true]| 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] |
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.
🔑 The Key Idea in the Code
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.
Putting
for k in range(n)inside theiandjloopsUsing
INT_MAXas "no path" in Java or C++Storing edge
[u, v]asdist[v][u]Writing
dist[u][v] = wfor parallel edgesA search per query: with up to
104queries, running a BFS fromufor each one repeats work the table does once; builddistfirst, then answer every query with the lookupdist[u][v] < float("inf").
4-Phase Thought Process Model
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: withkinside theiandjloops, in the chain0 -> 3 -> 2 -> 1the pair (0, 1) is finished beforedist[3][1]exists, and course 0 never reaches course 1.dist[u][v] = 1, notdist[v][u] = 1: the pair[ai, bi]putsaifirst, so the step runs fromaitobi.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.
Complexity & Mathematical Proof
O(V^3)
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: the table costs O(V^3), the card's bound. On top of it, each query is one O(1) lookup, O(Q) for all of them; with few courses and many queries that lookup total can be the larger part of the run.
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.
T(V, E, Q) = V^2 + E (build) + V^3 (triple loop) + Q (lookups) = O(V^3 + Q)
Derivation Progression
V^2 entries of inf, V zeros, E ones: O(V^2 + E)
Only direct steps are known before any stop is allowed.
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.
one lookup per query: O(Q)
The finished table answers any pair at once.
Variable Definitions
Number of courses, numCourses
Number of prerequisite pairs, len(prerequisites)
Number of queries, len(queries)
Memory Architecture & Bounds
O(1): three nested loops, no recursion
O(V^2): the V x V table dist
O(Q): one boolean per query, not counted as extra space
Boundary Best / Worst Cases
for the table: the triple loop runs in full on every input; then O(1) per query.
for the table, then O(1) per query.
for the table, then O(1) per query.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: a search per query costs up to steps, while the table costs checks once and then per query.
courses, pairs, queries. The table is entries, but grows fast: at it would be checks and entries.
At scale the 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.
Course Schedule IV (LeetCode 1462)
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
numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]][false,true][1, 0] is true; no chain leads from course 0 to course 1, so [0, 1] is false.numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]][false,false]numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]][true,true]⚖️Formal Constraints & Bounds
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != biAll the pairs
[ai, bi]are unique.The prerequisites graph has no cycles.
1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != vi
Core Insight
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
Fill a V x V table with inf, put 0 on the diagonal and 1 for every pair [u, v] (course u before course v).
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v in prerequisites:
dist[u][v] = 1Step-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, anddist[0][3] = dist[3][2] = dist[2][1] = 1; every other entry isinf. - 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, sodist[3][1] = 2. - Step 4 (k = 3): Pair (0, 1):
dist[0][3] + dist[3][1] = 1 + 2 = 3 < inf, sodist[0][1] = 3. This usesdist[3][1], built atk = 2: that is whykis the outermost loop. Pair (0, 2):1 + 1 = 2, sodist[0][2] = 2. - Step 5 (Answer the Queries):
dist[0][1] = 3is finite,dist[1][0] = inf,dist[3][1] = 2is finite: return[true, false, true]✅.
numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]Expected:[false,true]| 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] |
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.
🔑 The Key Idea in the Code
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.
Putting
for k in range(n)inside theiandjloopsUsing
INT_MAXas "no path" in Java or C++Storing edge
[u, v]asdist[v][u]Writing
dist[u][v] = wfor parallel edgesA search per query: with up to
104queries, running a BFS fromufor each one repeats work the table does once; builddistfirst, then answer every query with the lookupdist[u][v] < float("inf").
4-Phase Thought Process Model
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: withkinside theiandjloops, in the chain0 -> 3 -> 2 -> 1the pair (0, 1) is finished beforedist[3][1]exists, and course 0 never reaches course 1.dist[u][v] = 1, notdist[v][u] = 1: the pair[ai, bi]putsaifirst, so the step runs fromaitobi.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.
Complexity & Mathematical Proof
O(V^3)
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: the table costs O(V^3), the card's bound. On top of it, each query is one O(1) lookup, O(Q) for all of them; with few courses and many queries that lookup total can be the larger part of the run.
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.
T(V, E, Q) = V^2 + E (build) + V^3 (triple loop) + Q (lookups) = O(V^3 + Q)
Derivation Progression
V^2 entries of inf, V zeros, E ones: O(V^2 + E)
Only direct steps are known before any stop is allowed.
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.
one lookup per query: O(Q)
The finished table answers any pair at once.
Variable Definitions
Number of courses, numCourses
Number of prerequisite pairs, len(prerequisites)
Number of queries, len(queries)
Memory Architecture & Bounds
O(1): three nested loops, no recursion
O(V^2): the V x V table dist
O(Q): one boolean per query, not counted as extra space
Boundary Best / Worst Cases
for the table: the triple loop runs in full on every input; then O(1) per query.
for the table, then O(1) per query.
for the table, then O(1) per query.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: a search per query costs up to steps, while the table costs checks once and then per query.
courses, pairs, queries. The table is entries, but grows fast: at it would be checks and entries.
At scale the 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.