Problem Description

You are given numCourses courses labeled from 0 to numCourses - 1. Some courses have prerequisites - you must complete certain courses before you can take others.

The prerequisites are given as an array prerequisites where each element prerequisites[i] = [ai, bi] means you must take course ai before you can take course bi. For example, [0, 1] means course 0 must be completed before taking course 1.

Prerequisites can be indirect (transitive). If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is automatically a prerequisite of course c.

You need to answer multiple queries given in an array queries. Each query queries[j] = [uj, vj] asks: "Is course uj a prerequisite of course vj?" This includes both direct and indirect prerequisites.

Your task is to return a boolean array answer where answer[j] is true if course uj is a prerequisite (direct or indirect) of course vj, and false otherwise.

The solution uses Floyd-Warshall algorithm to find all transitive prerequisites. It creates a 2D boolean matrix f where f[i][j] represents whether course i is a prerequisite of course j. First, it marks all direct prerequisites from the input. Then, it uses three nested loops to find all indirect prerequisites: if course i is a prerequisite of k and k is a prerequisite of j, then i is a prerequisite of j. Finally, it answers each query by looking up the corresponding value in the matrix.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves courses (nodes) and prerequisites (directed edges). Each course is a node, and each prerequisite relationship forms a directed edge from one course to another.

Is it a tree?

• No: The prerequisite structure is not a tree. A course can have multiple prerequisites, and multiple courses can require the same prerequisite. This forms a directed graph that may contain multiple paths between nodes.

Is the problem related to directed acyclic graphs?

• Yes: The prerequisite relationships form a Directed Acyclic Graph (DAG). Courses cannot have circular dependencies (you can't have course A requiring B while B requires A), making this a DAG problem.

Topological Sort

• While topological sort could be used here, the specific problem asks about reachability (transitive closure) rather than ordering. We need to determine if one course is a prerequisite (direct or indirect) of another.

However, for this specific problem, we can also traverse the flowchart considering the connectivity aspect:

Does the problem involve connectivity?

• Yes: We need to determine if there's a path (direct or indirect prerequisite relationship) from one course to another.

Disjoint Set Union

• Not the best fit here as we need to know specific reachability between pairs of nodes, not just whether they're in the same connected component.

Does the problem have small constraints?

• Potentially yes (depending on the input size): This could lead us to DFS/backtracking.

DFS/backtracking

• Yes: DFS can be used to explore all paths from a source course to determine all courses it's a prerequisite for.

Conclusion: The flowchart suggests using DFS to solve this problem. We can use DFS to traverse from each course and mark all reachable courses (those that have it as a direct or indirect prerequisite). Alternatively, the solution shown uses Floyd-Warshall algorithm which finds all-pairs reachability efficiently.

Intuition

The key insight is recognizing that we need to find transitive relationships in a directed graph. When course A is a prerequisite of B, and B is a prerequisite of C, then A is also a prerequisite of C. This transitivity property is crucial.

Initially, we might think to use DFS for each query - starting from course u and checking if we can reach course v. However, this would be inefficient if we have many queries, as we'd need to perform a DFS for each one.

A better approach is to precompute all prerequisite relationships once, then answer each query in constant time. This is where Floyd-Warshall algorithm shines. It's designed specifically to find all shortest paths (or in our case, all reachability relationships) between every pair of nodes.

The algorithm works by considering each node as a potential "intermediate" stepping stone. For every pair of courses (i, j), we check: can we go from i to j by passing through an intermediate course k? If i can reach k (i is a prerequisite of k) and k can reach j (k is a prerequisite of j), then i can reach j (i is a prerequisite of j).

By systematically checking every possible intermediate course k for every pair (i, j), we build up the complete transitive closure - a matrix that tells us whether any course is a direct or indirect prerequisite of any other course. The beauty is that after this preprocessing step, answering each query becomes a simple lookup: just check f[u][v] to know if course u is a prerequisite of course v.

This trades preprocessing time (O(n³) for Floyd-Warshall) for extremely fast query answering (O(1) per query), which is ideal when we have multiple queries to answer.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

The solution implements Floyd-Warshall algorithm to compute the transitive closure of the prerequisite graph. Here's how the implementation works:

Step 1: Initialize the reachability matrix

f = [[False] * n for _ in range(n)]

We create a 2D boolean matrix f of size n × n, where f[i][j] will indicate whether course i is a prerequisite of course j. Initially, all values are False.

Step 2: Mark direct prerequisites

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

We iterate through the given prerequisites and mark the direct relationships. If course a is a direct prerequisite of course b, we set f[a][b] = True.

Step 3: Apply Floyd-Warshall algorithm

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

This is the core of the algorithm with three nested loops:

• Outer loop (k): Considers each course as a potential intermediate node
• Middle loop (i): Iterates through all possible starting courses
• Inner loop (j): Iterates through all possible ending courses

For each combination, we check: if course i can reach course k (meaning i is a prerequisite of k) AND course k can reach course j (meaning k is a prerequisite of j), then course i can reach course j through k. This captures the transitive property: if i → k and k → j, then i → j.

The order of loops is crucial - by putting k in the outermost loop, we ensure that when we consider k as an intermediate node, we've already processed all paths using intermediate nodes 0 through k-1.

Step 4: Answer queries

return [f[a][b] for a, b in queries]

After computing the complete transitive closure, answering each query is trivial. For each query [a, b], we simply look up f[a][b] to determine if course a is a prerequisite of course b.

The time complexity is O(n³) for the Floyd-Warshall preprocessing plus O(q) for answering q queries, giving O(n³ + q) total. The space complexity is O(n²) for the reachability matrix.

Example Walkthrough

Let's walk through a small example to illustrate how the Floyd-Warshall algorithm finds all prerequisite relationships.

Example Input:

• numCourses = 4 (courses labeled 0, 1, 2, 3)
• prerequisites = [[0,1], [1,2], [2,3]]
  • Course 0 must be taken before course 1
  • Course 1 must be taken before course 2
  • Course 2 must be taken before course 3
• queries = [[0,3], [2,0]]
  • Query 1: Is course 0 a prerequisite of course 3?
  • Query 2: Is course 2 a prerequisite of course 0?

Step 1: Initialize the matrix

f = [[F, F, F, F],
     [F, F, F, F],
     [F, F, F, F],
     [F, F, F, F]]

Step 2: Mark direct prerequisites After processing prerequisites:

f = [[F, T, F, F],  // 0→1
     [F, F, T, F],  // 1→2
     [F, F, F, T],  // 2→3
     [F, F, F, F]]

Step 3: Apply Floyd-Warshall (finding transitive relationships)

When k=0 (using course 0 as intermediate):

• Check all pairs (i,j): Can we go from i to j through 0?
• No new paths found (no course leads to 0)

When k=1 (using course 1 as intermediate):

• For i=0, j=2: f[0][1]=T and f[1][2]=T → Set f[0][2]=T
  • Course 0→1→2, so 0 is a prerequisite of 2

f = [[F, T, T, F],  // Added 0→2
     [F, F, T, F],
     [F, F, F, T],
     [F, F, F, F]]

When k=2 (using course 2 as intermediate):

• For i=0, j=3: f[0][2]=T and f[2][3]=T → Set f[0][3]=T
  • Course 0→2→3, so 0 is a prerequisite of 3
• For i=1, j=3: f[1][2]=T and f[2][3]=T → Set f[1][3]=T
  • Course 1→2→3, so 1 is a prerequisite of 3

f = [[F, T, T, T],  // Added 0→3
     [F, F, T, T],  // Added 1→3
     [F, F, F, T],
     [F, F, F, F]]

When k=3 (using course 3 as intermediate):

• No new paths found (no course from 3 leads anywhere)

Final matrix:

f = [[F, T, T, T],  // 0 is prerequisite of 1,2,3
     [F, F, T, T],  // 1 is prerequisite of 2,3
     [F, F, F, T],  // 2 is prerequisite of 3
     [F, F, F, F]]  // 3 is not prerequisite of any

Step 4: Answer queries

• Query [0,3]: Check f[0][3] = True ✓ (Course 0 is a prerequisite of 3)
• Query [2,0]: Check f[2][0] = False ✗ (Course 2 is not a prerequisite of 0)

Output: [True, False]

The algorithm successfully discovered that course 0 is an indirect prerequisite of course 3 (through the chain 0→1→2→3), even though it wasn't explicitly stated in the input.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n³)

The algorithm uses Floyd-Warshall to compute the transitive closure of the prerequisite graph. The triple nested loops iterate through all possible combinations of intermediate node k, source node i, and destination node j, each ranging from 0 to n-1. This results in n × n × n = n³ iterations. The operations inside the innermost loop (checking f[i][k] and f[k][j] and potentially setting f[i][j]) take constant time O(1). Additionally, initializing the adjacency matrix with prerequisites takes O(p) where p is the number of prerequisites, and processing queries takes O(q) where q is the number of queries. Since both p and q are at most O(n²), the overall time complexity is dominated by the Floyd-Warshall algorithm at O(n³).

Space Complexity: O(n²)

The algorithm creates a 2D boolean matrix f of size n × n to store whether there exists a path (direct or indirect) from node i to node j. This matrix requires O(n²) space. The output list stores boolean results for each query, requiring O(q) space where q is the number of queries. Since q is at most O(n²) and doesn't exceed the space used by matrix f, the overall space complexity is O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Loop Order in Floyd-Warshall Algorithm

The Pitfall: A common mistake is arranging the three nested loops in the wrong order. Developers might write:

# INCORRECT - Wrong loop order!
for i in range(n):
    for j in range(n):
        for k in range(n):
            if is_prerequisite[i][k] and is_prerequisite[k][j]:
                is_prerequisite[i][j] = True

This incorrect ordering fails to properly compute the transitive closure because when we check if i can reach j through k, we haven't yet considered all possible intermediate nodes for the paths i→k and k→j.

Why It Fails: The Floyd-Warshall algorithm requires that when considering node k as an intermediate node, all paths using intermediate nodes 0 through k-1 have already been computed. With the wrong loop order, we might miss indirect paths.

Example of Failure: Consider courses with prerequisites: [0→1], [1→2], [2→3]

• With incorrect loop order, when checking if 0→3 through intermediate node 2, we might not have discovered that 0→2 (through node 1) yet
• This leads to missing the transitive relationship 0→3

The Solution: Always place the intermediate node k in the outermost loop:

# CORRECT - Proper Floyd-Warshall loop order
for k in range(n):  # k must be the outermost loop
    for i in range(n):
        for j in range(n):
            if is_prerequisite[i][k] and is_prerequisite[k][j]:
                is_prerequisite[i][j] = True

This ensures that when we use k as an intermediate node, we've already processed all paths through nodes 0 to k-1, guaranteeing correct transitive closure computation.

2. Memory Optimization Temptation

The Pitfall: Attempting to optimize memory by updating the matrix in-place without proper consideration:

# RISKY - Trying to use a single row/column optimization
for k in range(n):
    for i in range(n):
        if is_prerequisite[i][k]:  # If i can reach k
            for j in range(n):
                is_prerequisite[i][j] = is_prerequisite[i][j] or is_prerequisite[k][j]

While this optimization works for Floyd-Warshall, it can be confusing and error-prone if not implemented carefully. The standard three-condition check is clearer and less prone to implementation errors.

The Solution: Stick with the clear, standard implementation unless memory is critically constrained. The readability and correctness are worth the theoretical redundancy in checks.