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.

  • For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. 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 the jth 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 jth query.

Examples

Example 1:

graph LR;
	1 --> 0
  
1
2
3
4

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.

Example 2:

1
2
3

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.

Example 3:

graph LR;
	1 --> 0
	1 --> 2
	2 --> 0
  
1
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 <= ai, bi <= numCourses - 1
  • ai != bi
  • All the pairs [ai, bi] are unique.
  • The prerequisites graph has no cycles.
  • 1 <= queries.length <= 104
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi

Solution

Method 1 - Floyd Warshall Algorithm

Here is the approach:

  1. Graph Representation: Represent the courses and their prerequisites as a directed graph where an edge from node a to node b (a -> b) means course a is a prerequisite for course b.
  2. Prerequisite Checking: To check if a course is a prerequisite of another, use the Floyd-Warshall algorithm which computes the transitive closure of the graph. The result of this algorithm can answer any query about the prerequisites between courses.
  3. Algorithm:
    • Create a matrix reachable where reachable[i][j] is True if course i is a prerequisite of course j.
    • Initialize the matrix: set reachable[a][b] to True for every prerequisite pair [a, b].
    • Use the Floyd-Warshall algorithm to compute the transitive closure, updating reachable[i][j] to True if there exists a course k such that reachable[i][k] and reachable[k][j] are both True.
    • For each query [u, v], check the value of reachable[u][v] to determine if u is a prerequisite of v.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reachable = new boolean[numCourses][numCourses];
        
        for (int[] pre : prerequisites) {
            reachable[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 (reachable[i][k] && reachable[k][j]) {
                        reachable[i][j] = true;
                    }
                }
            }
        }
        
        List<Boolean> ans = new ArrayList<>();
        for (int[] query : queries) {
            ans.add(reachable[query[0]][query[1]]);
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[Tuple[int, int]], queries: List[Tuple[int, int]]) -> List[bool]:
        reachable = [[False] * numCourses for _ in range(numCourses)]
        
        for pre in prerequisites:
            reachable[pre[0]][pre[1]] = True
        
        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    if reachable[i][k] and reachable[k][j]:
                        reachable[i][j] = True
        
        ans: List[bool] = []
        for u, v in queries:
            ans.append(reachable[u][v])
        
        return ans

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)