Scale Engineer

Course Schedule IV

Med
#1350Time: 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.
Algorithms
Depth-First SearchBreadth-First SearchTopological Sort
Data structures
Graph

Prompt

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.

 

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 <= 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

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 adj where adj.get(u) contains a list of courses v for which u is a direct prerequisite.
  • Initialize an empty list answer to store the boolean results.
  • For each query [u, v] in the queries array:
    • Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node u to check for reachability to v.
    • To perform BFS:
      • Initialize a queue and add the starting course u.
      • Use a visited boolean 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 current is the target course v, then a path exists. Add true to the answer list and break the search for this query.
      • Otherwise, for each neighbor of current in the adjacency list, if the neighbor has not been visited, mark it as visited and enqueue it.
    • If the traversal completes without finding v, it means v is not reachable from u. Add false to the answer list.
  • Return the answer list.

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:

  1. Construct the adjacency list from the prerequisites array.
  2. Initialize a list answer to store the results of the queries.
  3. Iterate through each query [u, v].
  4. For the current query, start a BFS (or DFS) from node u. A queue is used for BFS, and a visited set is maintained to avoid redundant computations and handle the graph structure efficiently.
  5. During the BFS, if we dequeue a node and it is the target node v, we have found a path. This confirms that u is a prerequisite for v. We add true to our answer list and move to the next query.
  6. If the BFS completes without finding v, it means there is no path from u to v. In this case, u is not a prerequisite for v, and we add false to the answer list.
  7. After processing all queries, return the answer list.
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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem