Course Schedule IV
MedPrompt
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 course0before you can take course1.
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.
Example 1:
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:
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.Example 3:
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]
Constraints:
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != bi- All the pairs
[ai, bi]are unique. - The prerequisites graph has no cycles.
1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != vi
Approaches
3 approaches with complexity analysis and trade-offs.
This approach treats each query independently. For every query [u, v], it performs a graph traversal, such as Breadth-First Search (BFS) or Depth-First Search (DFS), starting from the course u. The goal is to determine if course v is reachable from u. If v is encountered during the traversal, it means u is a prerequisite for v.
Algorithm
- Build an adjacency list
adjwhereadj.get(u)contains a list of coursesvfor whichuis a direct prerequisite. - Initialize an empty list
answerto store the boolean results. - For each query
[u, v]in thequeriesarray:- Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node
uto check for reachability tov. - To perform BFS:
- Initialize a queue and add the starting course
u. - Use a
visitedboolean array to keep track of visited nodes for the current query to avoid redundant processing. - While the queue is not empty, dequeue a course
current. - If
currentis the target coursev, then a path exists. Addtrueto theanswerlist and break the search for this query. - Otherwise, for each
neighborofcurrentin the adjacency list, if the neighbor has not been visited, mark it as visited and enqueue it.
- Initialize a queue and add the starting course
- If the traversal completes without finding
v, it meansvis not reachable fromu. Addfalseto theanswerlist.
- Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node
- Return the
answerlist.
Walkthrough
First, we represent the course prerequisites as a directed graph. An adjacency list is a suitable data structure, where adj[i] stores a list of courses that have i as a direct prerequisite.
The algorithm proceeds as follows:
- Construct the adjacency list from the
prerequisitesarray. - Initialize a list
answerto store the results of the queries. - Iterate through each query
[u, v]. - For the current query, start a BFS (or DFS) from node
u. A queue is used for BFS, and avisitedset is maintained to avoid redundant computations and handle the graph structure efficiently. - During the BFS, if we dequeue a node and it is the target node
v, we have found a path. This confirms thatuis a prerequisite forv. We addtrueto ouranswerlist and move to the next query. - If the BFS completes without finding
v, it means there is no path fromutov. In this case,uis not a prerequisite forv, and we addfalseto theanswerlist. - After processing all queries, return the
answerlist.
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[] p : prerequisites) { adj.get(p[0]).add(p[1]); } List<Boolean> ans = new ArrayList<>(); for (int[] q : queries) { ans.add(isReachable(q[0], q[1], numCourses, adj)); } return ans; } private boolean isReachable(int startNode, int endNode, int n, List<List<Integer>> adj) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; queue.offer(startNode); visited[startNode] = true; while (!queue.isEmpty()) { int curr = queue.poll(); if (curr == endNode) { return true; } for (int neighbor : adj.get(curr)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return false; }}Complexity
Time
O(Q * (N + P)), where Q is `queries.length`. For each of the Q queries, we perform a graph traversal (BFS/DFS) which takes O(N + P) time in the worst case.
Space
O(N + P), where N is `numCourses` and P is `prerequisites.length`. This space is used for storing the adjacency list. Each traversal also requires O(N) space for the queue and visited array.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Uses less memory than pre-computation approaches, which might be an advantage if memory is severely constrained and the number of queries is small.
Cons
Highly inefficient for a large number of queries, as it repeatedly traverses the same parts of the graph.
Very likely to cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits due to its high time complexity.
This approach improves upon the brute-force method by pre-computing all possible prerequisite relationships. The set of all reachability pairs in a graph is known as its transitive closure. The Floyd-Warshall algorithm is a classic dynamic programming algorithm that can compute this transitive closure. After an initial phase of pre-computation, each query can be answered in constant time.
Algorithm
- Initialize an
N x Nboolean matrixisReachable, whereNisnumCourses, with all values asfalse. - Populate the matrix with direct prerequisites. For each pair
[u, v]in theprerequisitesinput, setisReachable[u][v] = true. - Apply the Floyd-Warshall algorithm to find all-pairs reachability. This involves three nested loops:
- The outer loop iterates through an intermediate course
kfrom0toN-1. - The two inner loops iterate through all pairs of courses
(i, j)from0toN-1. - Inside the loops, update the reachability using the rule:
isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]). This checks if a path fromitojcan be formed by passing throughk.
- The outer loop iterates through an intermediate course
- After the loops complete,
isReachable[i][j]will betrueifjis reachable fromi(directly or indirectly). - For each query
[u, v], the answer is a direct O(1) lookup ofisReachable[u][v]. - Collect the results for all queries and return them.
Walkthrough
The core idea is to build a 2D boolean matrix, isReachable[i][j], which will be true if course i is a prerequisite for course j (i.e., j is reachable from i), and false otherwise.
The algorithm works as follows:
- Initialize an
N x Nboolean matrixisReachable, whereNisnumCourses. - Populate the matrix with direct prerequisites: for each pair
[u, v]inprerequisites, setisReachable[u][v] = true. - Apply the Floyd-Warshall algorithm. We iterate through all possible courses
kand consider them as intermediate nodes in a path. For every pair of courses(i, j), if there is a path fromitokand a path fromktoj, then there must be a path fromitoj. We updateisReachable[i][j]accordingly. The update rule is:isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]). - After the three nested loops complete, the
isReachablematrix contains the full transitive closure of the prerequisite graph. - Process the queries. For each query
[u, v], the answer is simply the value ofisReachable[u][v]. This is an O(1) lookup. - Collect the results and return them.
class Solution { public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { boolean[][] isReachable = new boolean[numCourses][numCourses]; for (int[] p : prerequisites) { isReachable[p[0]][p[1]] = true; } for (int k = 0; k < numCourses; k++) { for (int i = 0; i < numCourses; i++) { for (int j = 0; j < numCourses; j++) { isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]); } } } List<Boolean> ans = new ArrayList<>(); for (int[] q : queries) { ans.add(isReachable[q[0]][q[1]]); } return ans; }}Complexity
Time
O(N^3 + P + Q). The dominant part is the Floyd-Warshall algorithm with its three nested loops, which takes O(N^3). Initializing the matrix takes O(P), and answering all queries takes O(Q).
Space
O(N^2) to store the `isReachable` matrix.
Trade-offs
Pros
Extremely fast query time (O(1)) after the initial setup.
The implementation is relatively simple and consists of straightforward nested loops.
Guaranteed performance regardless of the graph's structure (density).
Cons
The O(N^3) time complexity for pre-computation can be slower than other methods if the graph is very sparse (i.e., P is much smaller than N^2).
Requires O(N^2) space, which could be a concern for problems with a very large number of courses.
This is another pre-computation approach that is often more efficient than Floyd-Warshall, especially for sparse graphs. Instead of using dynamic programming, we explicitly find all reachable nodes for each course by running a separate graph traversal (BFS or DFS) starting from every single course. This builds the same transitive closure information but can be faster depending on the graph's density.
Algorithm
- Build an adjacency list
adjfrom theprerequisitesarray. - Initialize an
N x Nboolean matrixisPrerequisiteto store the transitive closure, with all values initiallyfalse. - Iterate through each course
ifrom0toN-1.- For each
i, perform a graph traversal (like BFS) starting fromito find all courses that are reachable from it. - Use a queue for the BFS, starting with
i. - During the traversal, for every
neighborof thecurrentcourse, ifisPrerequisite[i][neighbor]isfalse, it means we haven't established this path yet. SetisPrerequisite[i][neighbor] = trueand add theneighborto the queue to explore its successors.
- For each
- After iterating through all
Nstarting courses, theisPrerequisitematrix is fully computed. - For each query
[u, v], the answer isisPrerequisite[u][v], which is an O(1) lookup. - Collect the results and return.
Walkthrough
Similar to the Floyd-Warshall approach, the goal is to pre-compute a data structure that allows for O(1) query time. Here, we also use a 2D matrix to store the transitive closure.
The algorithm is as follows:
- Build an adjacency list representation of the graph from the
prerequisites. - Create a
boolean[][] isPrerequisitematrix to store the transitive closure. - Iterate through each course
ifrom0tonumCourses - 1. - For each
i, perform a complete graph traversal (e.g., BFS) starting fromi. - During the traversal starting from
i, for every nodejthat is visited, it meansjis reachable fromi. We record this fact by settingisPrerequisite[i][j] = true. TheisPrerequisite[i]row itself can be used to track visited nodes for the traversal starting ati, avoiding the need for a separatevisitedarray in each iteration. - After iterating through all courses
i, theisPrerequisitematrix will be fully populated with all reachability information. - Process the queries by looking up the results in the
isPrerequisitematrix in O(1) time.
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[] p : prerequisites) { adj.get(p[0]).add(p[1]); } boolean[][] isPrerequisite = new boolean[numCourses][numCourses]; for (int i = 0; i < numCourses; i++) { // Perform BFS from each node to find all reachable nodes Queue<Integer> queue = new LinkedList<>(); queue.offer(i); // No need for a separate visited array, we can use the isPrerequisite[i] row while (!queue.isEmpty()) { int curr = queue.poll(); for (int neighbor : adj.get(curr)) { if (!isPrerequisite[i][neighbor]) { isPrerequisite[i][neighbor] = true; queue.offer(neighbor); } } } } List<Boolean> ans = new ArrayList<>(); for (int[] q : queries) { ans.add(isPrerequisite[q[0]][q[1]]); } return ans; }}Complexity
Time
O(N * (N + P) + Q). We run N traversals. Each traversal takes at most O(N + P) time. For sparse graphs, this is closer to O(N*P), which is better than Floyd-Warshall's O(N^3). For dense graphs, the complexity approaches O(N^3).
Space
O(N^2 + P). We need O(N+P) for the adjacency list and O(N^2) for the `isPrerequisite` matrix.
Trade-offs
Pros
Generally the most efficient approach for the given constraints.
Significantly faster than Floyd-Warshall for sparse graphs (where P << N^2).
Provides O(1) query time after the pre-computation is complete.
Cons
The implementation is slightly more complex than Floyd-Warshall, as it involves graph data structures (adjacency list) and traversal logic.
Still requires O(N^2) space, which can be large.
Solutions
Solution
class Solution {public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { boolean[][] f = new boolean[n][n]; for (var p : prerequisites) { f[p[0]][p[1]] = true; } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { f[i][j] |= f[i][k] && f[k][j]; } } } List<Boolean> ans = new ArrayList<>(); for (var q : queries) { ans.add(f[q[0]][q[1]]); } return ans; }}class Solution {public: vector<bool> checkIfPrerequisite(int n, vector<vector<int>> &prerequisites, vector<vector<int>> &queries) { bool f[n][n]; memset(f, false, sizeof(f)); for (auto &p : prerequisites) { f[p[0]][p[1]] = true; } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { f[i][j] |= (f[i][k] && f[k][j]); } } } vector<bool> ans; for (auto &q : queries) { ans.push_back(f[q[0]][q[1]]); } return ans; }};class Solution: def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: f = [[False] * n for _ in range(n)] for a, b in prerequisites: f[a][b] = True 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 return [f[a][b] for a, b in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.