Code Implementation

class Solution:
    def checkIfPrerequisite(self, numCourses, prerequisites, queries):
        # Build adjacency list
        graph = [[] for _ in range(numCourses)]
        for u, v in prerequisites:
            graph[u].append(v)

        # Floyd-Warshall for reachability
        reach = [[False] * numCourses for _ in range(numCourses)]
        for u in range(numCourses):
            for v in graph[u]:
                reach[u][v] = True

        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    if reach[i][k] and reach[k][j]:
                        reach[i][j] = True

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

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>> reach(numCourses, vector<bool>(numCourses, false));
        for (auto& pre : prerequisites) {
            reach[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 (reach[i][k] && reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }
        vector<bool> res;
        for (auto& q : queries) {
            res.push_back(reach[q[0]][q[1]]);
        }
        return res;
    }
};
      

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[numCourses][numCourses];
        for (int[] pre : prerequisites) {
            reach[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 (reach[i][k] && reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }
        List<Boolean> res = new ArrayList<>();
        for (int[] q : queries) {
            res.add(reach[q[0]][q[1]]);
        }
        return res;
    }
}
      

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    const reach = Array.from({length: numCourses}, () => Array(numCourses).fill(false));
    for (const [u, v] of prerequisites) {
        reach[u][v] = true;
    }
    for (let k = 0; k < numCourses; ++k) {
        for (let i = 0; i < numCourses; ++i) {
            for (let j = 0; j < numCourses; ++j) {
                if (reach[i][k] && reach[k][j]) {
                    reach[i][j] = true;
                }
            }
        }
    }
    return queries.map(([u, v]) => reach[u][v]);
};
      

Problem Description

You are given an integer numCourses, representing the number of courses labeled from 0 to numCourses - 1. You are also given a list of prerequisite pairs prerequisites, where each pair [a, b] means course a must be taken before course b.
Additionally, you have a list of queries queries, where each query is a pair [u, v] asking whether taking course u is a prerequisite (direct or indirect) for course v.
For each query, return true if u is a prerequisite of v, otherwise return false.
Constraints:

• Each course is uniquely labeled from 0 to numCourses - 1.
• You must answer all queries efficiently.
• There may be cycles or disconnected components.

Thought Process

At first glance, the problem looks similar to checking if there is a path from one node to another in a directed graph. For each query, we need to find out if there is a sequence of prerequisites leading from u to v. A brute-force way would be to run a depth-first search (DFS) or breadth-first search (BFS) for every query, but since there could be many queries, this would be inefficient.
The key realization is that since the set of courses and prerequisites is fixed, we can preprocess the entire reachability (prerequisite) information for all pairs of courses. Once we know for every pair whether one is a prerequisite for another, we can answer each query in constant time.
This is a classic case for using the Floyd-Warshall algorithm, which computes reachability between all pairs in a directed graph efficiently.

Solution Approach

To solve this problem efficiently, we use the following steps:

1. Represent the graph: Build an adjacency list or matrix to represent the prerequisite relationships between courses.
2. Initialize reachability: Create a 2D boolean matrix reach where reach[u][v] is true if course u is a direct prerequisite of v.
3. Compute indirect prerequisites: Use the Floyd-Warshall algorithm to update reach so that reach[u][v] is true if u is a direct or indirect prerequisite of v. This is done by checking, for every triple (i, k, j), if i can reach k and k can reach j, then i can reach j.
4. Answer queries: For each query [u, v], simply return reach[u][v].

We use a 2D matrix because it allows for constant-time lookups and is suitable given the constraints (typically, numCourses is not extremely large).

Example Walkthrough

Suppose numCourses = 4, prerequisites = [[0,1],[1,2],[2,3]], and queries = [[0,3],[1,3],[3,0],[0,2]].
Step 1: Initial direct prerequisites:

• 0 → 1
• 1 → 2
• 2 → 3

• 0 is a prerequisite for 1, 2, and 3
• 1 is a prerequisite for 2 and 3
• 2 is a prerequisite for 3

• [0,3]: Yes, 0 → 1 → 2 → 3 exists (true)
• [1,3]: Yes, 1 → 2 → 3 exists (true)
• [3,0]: No path from 3 to 0 (false)
• [0,2]: Yes, 0 → 1 → 2 exists (true)

Time and Space Complexity

Brute-force approach: For each query, perform BFS/DFS, which is O(Q * (N + E)) where Q is the number of queries, N is the number of courses, and E the number of prerequisites. This is inefficient for large Q.
Optimized approach (Floyd-Warshall):

• Time: O(N^3 + Q) — O(N^3) for Floyd-Warshall, O(Q) for answering queries
• Space: O(N^2) for the reachability matrix

Summary

The key to solving Course Schedule IV efficiently is recognizing that we can preprocess all prerequisite relationships using the Floyd-Warshall algorithm. This allows us to answer each query in constant time, rather than searching the graph repeatedly. By representing the problem as a graph and leveraging classic graph algorithms, we achieve both clarity and efficiency in our solution.