Course Schedule IV: Transitive Closure with Floyd-Warshall

You are given numCourses (labeled 0 to numCourses - 1), a list of prerequisites pairs where each pair [a, b] means course a is a prerequisite of course b, and a list of queries where each query [u, v] asks: "Is course u a direct or indirect prerequisite of course v?" Return a boolean answer for every query.

This is LeetCode 1462: Course Schedule IV, and it comes down to precomputing all reachability relationships in a directed graph so that each query can be answered instantly.

Prerequisite graph

Course 0 is a prerequisite for 1 and 2. Courses 1 and 2 are both prerequisites for 3.

Reachability matrix

	0	1	2	3
0	F	T	T	T
1	F	F	F	T
2	F	F	F	T
3	F	F	F	F

reachable[i][j] = True means course i is a prerequisite of course j. Any query is answered in O(1).

Why this problem matters

The earlier Course Schedule problems ask whether a valid ordering exists (cycle detection) or what that ordering is (topological sort). Course Schedule IV shifts the focus: given that the ordering exists, can you efficiently answer many questions about which courses are prerequisites of which other courses?

This is the classic graph reachability problem, also known as computing the transitive closure of a directed graph. In real systems, transitive closure shows up in access control (can user A reach permission B through a chain of group memberships?), dependency analysis (does changing library X affect service Y?), and ontology reasoning (is category A a subcategory of category B, possibly through many layers?).

The naive approach would be to run a BFS or DFS for each query independently. That works, but if you have many queries, you repeat a lot of work. The smarter move is to precompute all pairwise reachability once, then answer every query in O(1) time with a simple table lookup.

The key insight

Build an n x n boolean matrix called reachable where reachable[i][j] = True means course i is a prerequisite of course j (directly or through a chain of intermediaries). First, seed the matrix with the direct edges: for each pair [a, b] in prerequisites, set reachable[a][b] = True. Then apply the Floyd-Warshall transitive closure technique: for each possible intermediate node k, scan every pair (i, j). If reachable[i][k] and reachable[k][j] are both true, then i can reach j through k, so set reachable[i][j] = True.

After three nested loops over n nodes, the matrix captures every direct and indirect prerequisite relationship. Each query [u, v] is answered by returning reachable[u][v].

The solution

def check_if_prerequisite(
    num_courses: int,
    prerequisites: list[list[int]],
    queries: list[list[int]],
) -> list[bool]:
    reachable = [[False] * num_courses for _ in range(num_courses)]

    for a, b in prerequisites:
        reachable[a][b] = True

    for k in range(num_courses):
        for i in range(num_courses):
            for j in range(num_courses):
                if reachable[i][k] and reachable[k][j]:
                    reachable[i][j] = True

    return [reachable[u][v] for u, v in queries]

The structure is clean. First we create an n x n matrix initialized to False. Then we mark each direct prerequisite edge as True. The triple loop is the heart of Floyd-Warshall: for every intermediate node k, for every source i and destination j, if there is a path from i to k and a path from k to j, then there is a path from i to j.

After the loop finishes, the matrix is the full transitive closure. Answering queries is just indexing into the 2D array.

Note that Floyd-Warshall requires the outermost loop to iterate over the intermediate node k. This ordering is important. If you put k in the inner loop, the algorithm does not correctly propagate paths through chains of intermediate nodes.

Visual walkthrough

Here is how Floyd-Warshall builds the reachability matrix step by step for a graph with 4 courses and prerequisites [[0,1],[0,2],[1,3],[2,3]].

Each iteration of k asks: "Can I discover a new path by routing through node k?" When k = 1, we find that node 0 reaches node 1, and node 1 reaches node 3, so node 0 must also reach node 3. That single discovery fills in the last missing cell. The remaining iterations confirm nothing new, and the matrix is complete.

Complexity analysis

Here n is numCourses, e is the number of prerequisite edges, and q is the number of queries.

Time: Floyd-Warshall uses three nested loops over n, giving O(n^3) for precomputation. Each query is O(1), so answering all queries costs O(q). Total: O(n^3 + q). BFS from each node costs O(n + e) per source node, for O(n * (n + e)) total, plus O(q) for queries.

Space: Both approaches store the n x n reachability matrix, costing O(n^2). BFS also needs a queue and visited set per run, but those are O(n) each and reused, so the dominant cost remains O(n^2).

The building blocks

1. Transitive closure with Floyd-Warshall

for k in range(n):
    for i in range(n):
        for j in range(n):
            if reachable[i][k] and reachable[k][j]:
                reachable[i][j] = True

This is a boolean adaptation of the Floyd-Warshall shortest-path algorithm. Instead of minimizing distances, you propagate reachability. The key invariant is that after processing intermediate node k, the matrix correctly reflects all paths that use only nodes 0 through k as intermediaries. By the time k has swept through every node, all paths are accounted for.

2. Constant-time query answering

return [reachable[u][v] for u, v in queries]

Once the matrix is built, every query becomes a direct lookup. This is the payoff of precomputation: you do O(n^3) work up front so that each of the potentially many queries costs O(1). If the problem gave you a single query, BFS from the source would be faster. But with many queries, amortizing the precomputation cost wins.

Edge cases

• No prerequisites: The reachability matrix stays all False. Every query returns False.
• Single course: numCourses = 1, no edges. The only possible query is [0, 0], which returns False (a course is not its own prerequisite).
• Linear chain: 0 -> 1 -> 2 -> ... -> n-1. The matrix has True for every (i, j) where i is less than j. Floyd-Warshall fills it in as k sweeps forward.
• Disconnected components: Courses with no path between them always return False. The algorithm handles this naturally since their matrix entries are never set.
• No queries: Return an empty list. The precomputation still runs, but there is nothing to answer.

From understanding to recall

The Floyd-Warshall transitive closure is one of those algorithms that fits in about five lines of code, but getting those five lines right under pressure takes practice. The loop order matters (k outermost), the initialization matters (seed with direct edges, not all False), and the boolean logic is subtly different from the shortest-path version you may have memorized.

Spaced repetition turns this from "I remember the concept" into "I can write it cold." You practice the triple loop, the matrix seeding, and the query phase separately until each piece is automatic. Then when you see a reachability problem in an interview, you recognize the pattern and write it without hesitation.

Related posts

• Course Schedule - Detecting cycles in a prerequisite graph using DFS and topological sort
• Course Schedule II - Producing the actual topological ordering of courses
• Number of Provinces - Counting connected components, a simpler form of graph connectivity

Floyd-Warshall is a small algorithm with broad reach. Master the five-line loop and you unlock transitive closure, all-pairs shortest paths, and a whole family of graph precomputation problems. Course Schedule IV is your entry point.