Course Schedule IV

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogle

Problem Description

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] = [ui, vi] indicates that you must take course ui before course vi.

Prerequisites are transitive: if course A is a prerequisite of course B, and course B is a prerequisite of course C, then course A is a prerequisite of course C.

You are also given an array queries where queries[j] = [uj, vj]. For each query j, answer whether course uj is a prerequisite of course vj.

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

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true] Explanation: The database shows that course 1 must be taken before course 0. So 0 is not a prerequisite of 1 (false), but 1 is a prerequisite of 0 (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
0 ≤ ui, vi < numCourses
ui != vi
All pairs [ui, vi] are distinct
1 ≤ queries.length ≤ 10⁴
queries[j].length == 2
0 ≤ uj, vj < numCourses
uj != vj

Reachability Matrix

Because numCourses is very small (≤ 100), we can build a full reachability matrix where reachable[i][j] is true if i is a prerequisite of j.

We can populate this matrix using the Floyd-Warshall algorithm in O(V³) time. For every intermediate course k, if i reaches k and k reaches j, then i reaches j. Once populated, each query is answered in O(1) time.

Solution 1: Floyd-Warshall (O(V³) Precomputation)

import java.util.*;

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] isPre = new boolean[numCourses][numCourses];

        for (int[] pre : prerequisites) {
            isPre[pre[0]][pre[1]] = true;
        }

        // Floyd-Warshall transitive closure
        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    if (isPre[i][k] && isPre[k][j]) {
                        isPre[i][j] = true;
                    }
                }
            }
        }

        List<Boolean> result = new ArrayList<>();
        for (int[] q : queries) {
            result.add(isPre[q[0]][q[1]]);
        }
        return result;
    }
}

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: list[list[int]],
                           queries: list[list[int]]) -> list[bool]:
        is_pre = [[False] * numCourses for _ in range(numCourses)]

        for src, dest in prerequisites:
            is_pre[src][dest] = True

        # Floyd-Warshall transitive closure
        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    if is_pre[i][k] and is_pre[k][j]:
                        is_pre[i][j] = True

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

#include <vector>

class Solution {
public:
    std::vector<bool> checkIfPrerequisite(int numCourses, std::vector<std::vector<int>>& prerequisites,
                                          std::vector<std::vector<int>>& queries) {
        std::vector<std::vector<bool>> isPre(numCourses, std::vector<bool>(numCourses, false));

        for (const auto& pre : prerequisites) {
            isPre[pre[0]][pre[1]] = true;
        }

        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    if (isPre[i][k] && isPre[k][j]) {
                        isPre[i][j] = true;
                    }
                }
            }
        }

        std::vector<bool> result;
        for (const auto& q : queries) {
            result.push_back(isPre[q[0]][q[1]]);
        }
        return result;
    }
};

Complexity Analysis:

Time Complexity: O(V³ + Q) where V is numCourses and Q is the number of queries. Floyd-Warshall runs in O(V³) time, which is fast when V ≤ 100 (1 million iterations).
Space Complexity: O(V²) to store the reachability matrix.

Where it breaks: if numCourses were larger (e.g., 2000), Floyd-Warshall’s O(V³) time complexity (8 billion operations) would time out. In that case, doing a BFS/DFS from each node to build prerequisite sets is better, running in O(V * (V + E)).

Solution 2: BFS Precomputation (O(V * (V + E)))

Do a BFS from each course i to find all descendant courses, marking isPre[i][j] = true for each visited course j.

import java.util.*;

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) {
            adj.get(pre[0]).add(pre[1]);
        }

        boolean[][] isPre = new boolean[numCourses][numCourses];

        // run BFS from each node
        for (int i = 0; i < numCourses; i++) {
            Queue<Integer> q = new LinkedList<>();
            q.offer(i);
            while (!q.isEmpty()) {
                int curr = q.poll();
                for (int neighbor : adj.get(curr)) {
                    if (!isPre[i][neighbor]) {
                        isPre[i][neighbor] = true;
                        q.offer(neighbor);
                    }
                }
            }
        }

        List<Boolean> result = new ArrayList<>();
        for (int[] q : queries) {
            result.add(isPre[q[0]][q[1]]);
        }
        return result;
    }
}

from collections import deque

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: list[list[int]],
                           queries: list[list[int]]) -> list[bool]:
        adj = [[] for _ in range(numCourses)]
        for src, dest in prerequisites:
            adj[src].append(dest)

        is_pre = [[False] * numCourses for _ in range(numCourses)]

        for i in range(numCourses):
            queue = deque([i])
            while queue:
                curr = queue.popleft()
                for neighbor in adj[curr]:
                    if not is_pre[i][neighbor]:
                        is_pre[i][neighbor] = True
                        queue.append(neighbor)

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

#include <vector>
#include <queue>

class Solution {
public:
    std::vector<bool> checkIfPrerequisite(int numCourses, std::vector<std::vector<int>>& prerequisites,
                                          std::vector<std::vector<int>>& queries) {
        std::vector<std::vector<int>> adj(numCourses);
        for (const auto& pre : prerequisites) {
            adj[pre[0]].push_back(pre[1]);
        }

        std::vector<std::vector<bool>> isPre(numCourses, std::vector<bool>(numCourses, false));

        for (int i = 0; i < numCourses; i++) {
            std::queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int curr = q.front(); q.pop();
                for (int neighbor : adj[curr]) {
                    if (!isPre[i][neighbor]) {
                        isPre[i][neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }

        std::vector<bool> result;
        for (const auto& q : queries) {
            result.push_back(isPre[q[0]][q[1]]);
        }
        return result;
    }
};