Course Schedule IV

Difficulty: Medium Source: NeetCode

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

You are also given an array queries where queries[j] = [uj, vj]. For the j-th query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the j-th query.

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

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

Constraints:

• 2 <= numCourses <= 100
• 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
• prerequisites[i].length == 2, no duplicates, no self-loops
• 1 <= queries.length <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Graph reachability — can node u reach node v via directed edges?
• Topological sort — processing nodes in dependency order
• Floyd-Warshall — all-pairs reachability in a directed graph

1. BFS for Each Query

Intuition

For each query (u, v), run BFS from u on the directed graph and check if v is reachable. Simple and correct, but O(Q * (V + E)) which can be slow for many queries.

Algorithm

1. Build adjacency list from prerequisites.
2. For each query (u, v), run BFS from u.
3. Return True if v was reached, else False.

Solution

from collections import deque

def checkIfPrerequisite(numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]:
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[a].append(b)

    def can_reach(src, dst):
        visited = {src}
        queue = deque([src])
        while queue:
            node = queue.popleft()
            if node == dst:
                return True
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return False

    return [can_reach(u, v) for u, v in queries]


print(checkIfPrerequisite(2, [[1,0]], [[0,1],[1,0]]))              # [False, True]
print(checkIfPrerequisite(3, [[1,2],[1,0],[2,0]], [[1,0],[1,2]]))  # [True, True]

Complexity

• Time: O(Q * (V + E)) where Q = number of queries
• Space: O(V + E)

2. Floyd-Warshall Reachability (Optimal for Many Queries)

Intuition

Precompute all-pairs reachability using a boolean matrix reach[i][j] = True if course i is a prerequisite (direct or indirect) of course j. This is essentially Floyd-Warshall adapted for reachability instead of distance.

Build the matrix: first mark direct prerequisites. Then, for each intermediate node k, update: if i can reach k and k can reach j, then i can reach j. After precomputation, each query is answered in O(1).

Algorithm

1. Initialize reach[i][j] = False for all pairs.
2. For each direct prerequisite (a, b): set reach[a][b] = True.
3. For each k from 0 to n-1: for each i, for each j: if reach[i][k] and reach[k][j], set reach[i][j] = True.
4. Answer each query (u, v) with reach[u][v].

Solution

def checkIfPrerequisite(numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]:
    n = numCourses
    reach = [[False] * n for _ in range(n)]

    # Direct prerequisites
    for a, b in prerequisites:
        reach[a][b] = True

    # Floyd-Warshall for transitive reachability
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if reach[i][k] and reach[k][j]:
                    reach[i][j] = True

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


print(checkIfPrerequisite(2, [[1,0]], [[0,1],[1,0]]))              # [False, True]
print(checkIfPrerequisite(3, [[1,2],[1,0],[2,0]], [[1,0],[1,2]]))  # [True, True]
print(checkIfPrerequisite(4, [[0,1],[1,2],[2,3]], [[0,3],[3,0]]))  # [True, False]

Complexity

• Time: O(V³ + Q) — V³ for Floyd-Warshall, Q for answering queries
• Space: O(V²) for the reachability matrix

3. Topological Sort + DFS Reachability

Intuition

Process nodes in topological order. For each node, compute its full reachability set (the set of nodes it can reach). A node’s reachability is the union of all its direct prerequisites’ reachability sets, plus those direct prerequisites themselves. Processing in topological order ensures that when we process a node, all its prerequisites are already fully computed.

Solution

from collections import deque

def checkIfPrerequisite(numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]:
    n = numCourses
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    prereqs = [set() for _ in range(n)]  # prereqs[v] = set of courses that are prerequisites of v

    for a, b in prerequisites:
        graph[a].append(b)
        in_degree[b] += 1

    # Kahn's topological sort
    queue = deque(i for i in range(n) if in_degree[i] == 0)

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            prereqs[neighbor].add(node)
            prereqs[neighbor] |= prereqs[node]  # propagate transitive prerequisites
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

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


print(checkIfPrerequisite(2, [[1,0]], [[0,1],[1,0]]))              # [False, True]
print(checkIfPrerequisite(3, [[1,2],[1,0],[2,0]], [[1,0],[1,2]]))  # [True, True]

Complexity

• Time: O(V² + E + Q) — set union at each node can be O(V)
• Space: O(V²) for the prereqs sets

Common Pitfalls

Edge direction in prerequisites. prerequisites[i] = [a, b] means a must come before b — so the edge goes from a to b. Don’t accidentally reverse it when building the graph.

Floyd-Warshall loop order. The k (intermediate) loop must be the outermost. If you put i or j first, you’ll miss some transitive paths because you’ll be checking for intermediates that haven’t been fully processed yet.

Self-reachability. A node is not considered a prerequisite of itself unless explicitly stated. reach[i][i] = False by default, which is correct for this problem.