Course Schedule IV

Description

You are given a total of numCourses courses, labeled from 0 to numCourses - 1. Some courses have prerequisite requirements: you must complete certain courses before you can take others.

You receive an array prerequisites where each element prerequisites[i] = [a, b] means that course a must be completed before course b can be taken. 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 also considered a prerequisite of course c.

You are also given an array of queries where each queries[j] = [u, v] asks whether course u is a prerequisite (directly or indirectly) of course v.

Return a boolean array where the j-th element is true if course u is a prerequisite of course v, and false otherwise.

Directed acyclic graph showing course prerequisite relationships for a 3-course example

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

Output: [false, true]

Explanation: The prerequisite [1, 0] means course 1 must be taken before course 0 — so course 1 is a prerequisite of course 0. For query [0,1]: course 0 is NOT a prerequisite of course 1, so the answer is false. For query [1,0]: course 1 IS a prerequisite of course 0 (directly), so the answer is true.

Example 2

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]

Output: [false, false]

Explanation: There are no prerequisites at all. No course depends on any other course. Both queries return false because there are no prerequisite relationships.

Example 3

Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]

Output: [true, true]

Explanation: Course 1 is a direct prerequisite of both courses 2 and 0. Course 2 is a direct prerequisite of course 0. For query [1,0]: course 1 is a prerequisite of course 0 (directly via edge 1→0, and also indirectly via 1→2→0). For query [1,2]: course 1 is a direct prerequisite of course 2. Both answers are true.

Constraints

2 ≤ numCourses ≤ 100
0 ≤ prerequisites.length ≤ (numCourses × (numCourses - 1) / 2)
prerequisites[i].length == 2
0 ≤ a_i, b_i ≤ numCourses - 1
a_i ≠ b_i
All pairs [a_i, b_i] are unique
The prerequisites graph has no cycles
1 ≤ queries.length ≤ 10^4
0 ≤ u_j, v_j ≤ numCourses - 1
u_j ≠ v_j

Editorial

Brute Force

Intuition

The most natural way to check whether course u is a prerequisite of course v is to explore the prerequisite graph starting from u and see if we can eventually reach v.

Imagine you are standing at course u in a network of one-way hallways. Each hallway represents a direct prerequisite relationship. To answer the query, you simply walk through every hallway you can find, checking room numbers along the way. If you ever walk into room v, the answer is yes. If you exhaust all reachable rooms without finding v, the answer is no.

This is exactly what Depth-First Search (DFS) does: starting from a node, it explores as deep as possible along each branch before backtracking. For each query, we launch a fresh DFS from the source node and check whether the target is reachable.

Step-by-Step Explanation

Let's trace through Example 3: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]].

First, build the adjacency list:

adj[0] = [] (no outgoing edges from course 0)
adj[1] = [2, 0] (course 1 is prerequisite of 2 and 0)
adj[2] = [0] (course 2 is prerequisite of 0)

Query 1: Is course 1 a prerequisite of course 0?

Step 1: Start DFS from node 1. Mark node 1 as visited. Is node 1 the target (0)? No.

Step 2: Explore neighbor 2 (via edge 1→2). Move to node 2.

Step 3: Mark node 2 as visited. Is node 2 the target (0)? No. Explore its neighbors.

Step 4: Explore neighbor 0 (via edge 2→0). Move to node 0.

Step 5: Node 0 is the target! We found a path: 1→2→0. Return true.

Step 6: For query [1,2], we must run a completely new DFS from node 1 with a fresh visited set. This repeated work is the core inefficiency.

Result: [true, true]

DFS Per Query — Checking if Course 1 Reaches Course 0 — Watch how DFS explores the directed prerequisite graph from the source node, traversing edges until it finds the target or exhausts all paths.

Algorithm

Build an adjacency list from the prerequisites array: for each [a, b], add b to adj[a]
For each query [u, v]:
a. Create a fresh visited set
b. Run DFS starting from node u
c. If DFS reaches node v, record true; otherwise record false
Return the array of boolean results

Code

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<int>> adj(numCourses);
        for (auto& p : prerequisites) {
            adj[p[0]].push_back(p[1]);
        }
        
        vector<bool> result;
        for (auto& q : queries) {
            vector<bool> visited(numCourses, false);
            result.push_back(dfs(adj, q[0], q[1], visited));
        }
        return result;
    }
    
    bool dfs(vector<vector<int>>& adj, int src, int target, vector<bool>& visited) {
        if (src == target) return true;
        visited[src] = true;
        for (int next : adj[src]) {
            if (!visited[next] && dfs(adj, next, target, visited)) {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]:
        adj = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            adj[a].append(b)
        
        def dfs(src, target, visited):
            if src == target:
                return True
            visited.add(src)
            for next_node in adj[src]:
                if next_node not in visited and dfs(next_node, target, visited):
                    return True
            return False
        
        result = []
        for u, v in queries:
            result.append(dfs(u, v, set()))
        return result

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> result = new ArrayList<>();
        for (int[] q : queries) {
            boolean[] visited = new boolean[numCourses];
            result.add(dfs(adj, q[0], q[1], visited));
        }
        return result;
    }
    
    private boolean dfs(List<List<Integer>> adj, int src, int target, boolean[] visited) {
        if (src == target) return true;
        visited[src] = true;
        for (int next : adj.get(src)) {
            if (!visited[next] && dfs(adj, next, target, visited)) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(q × (V + E))

For each of the q queries, we run a DFS that visits up to V nodes and traverses up to E edges. With q up to 10^4 and V up to 100 (meaning E up to ~5,000), the worst case is approximately 10^4 × 5,100 = 5.1 × 10^7 operations — borderline for tight time limits.

Space Complexity: O(V + E)

The adjacency list stores E edges across V lists. Each DFS call uses a visited array of size V and up to V recursive call stack frames. The visited array is recreated for each query but does not accumulate.

Why This Approach Is Not Efficient

The brute force runs a completely independent DFS for every single query. With up to 10,000 queries and a graph of 100 nodes, we potentially traverse the same edges tens of thousands of times.

The fundamental flaw is redundant computation: if query 1 asks "Is 0 a prerequisite of 3?" and query 2 asks "Is 0 a prerequisite of 2?", the DFS for both queries will explore many of the same nodes and edges starting from node 0. Yet we throw away all that exploration after each query and start fresh.

The key insight is: instead of answering queries on-demand, we can precompute all reachability information upfront. If we know, for every pair of courses (i, j), whether i can reach j, then answering any query becomes an instant O(1) table lookup. The next approach does exactly this — run BFS from each node once, storing all reachability results in a matrix.

Better Approach - BFS Precomputation

Intuition

Instead of redoing graph traversal for each query, we can precompute all reachability information at once. The idea is simple: for every course i, run a BFS (Breadth-First Search) to discover all courses reachable from i. Store these results in a 2D boolean matrix reach[i][j] — true if course i can reach course j.

Think of it like creating a complete contact directory before answering phone calls. Instead of looking up each person's number from scratch every time someone calls, you build the entire directory once. After that, answering any "Can person A reach person B?" question is instant — just check the directory.

With the reachability matrix precomputed, each query [u, v] is answered in O(1) by simply returning reach[u][v].

Step-by-Step Explanation

Let's trace with Example 3: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]].

Adjacency list: adj[0] = [], adj[1] = [2, 0], adj[2] = [0].

Step 1: Initialize a 3×3 reachability matrix, all values false.

Step 2: BFS from node 0. Node 0 has no outgoing edges. Nothing is reachable from course 0.

Step 3: BFS from node 1. Start: queue = [1]. Dequeue 1, neighbors: [2, 0]. Enqueue both. Mark reach[1][2] = true and reach[1][0] = true.

Step 4: Dequeue 2. Neighbor of 2: [0]. reach[1][0] is already true, so no new discovery.

Step 5: Dequeue 0. No outgoing edges. BFS from node 1 complete. Reachable from 1: {2, 0}.

Step 6: BFS from node 2. Start: queue = [2]. Dequeue 2, neighbor: [0]. Mark reach[2][0] = true.

Step 7: Dequeue 0. No outgoing edges. BFS from 2 complete. Reachable from 2: {0}.

Step 8: Precomputation done. Answer queries from matrix:

Query [1,0]: reach[1][0] = true
Query [1,2]: reach[1][2] = true
Result: [true, true]

BFS Precomputation — Discovering All Reachable Courses — Watch as BFS runs from each node, building a complete reachability matrix so every future query can be answered in O(1).

Algorithm

Build an adjacency list from the prerequisites
Create a V×V boolean matrix reach, initialized to all false
For each node i from 0 to V-1:
a. Run BFS starting from node i
b. For every node j discovered during BFS, set reach[i][j] = true
For each query [u, v], return reach[u][v]

Code

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<int>> adj(numCourses);
        for (auto& p : prerequisites) {
            adj[p[0]].push_back(p[1]);
        }
        
        vector<vector<bool>> reach(numCourses, vector<bool>(numCourses, false));
        for (int i = 0; i < numCourses; i++) {
            queue<int> q;
            q.push(i);
            vector<bool> visited(numCourses, false);
            visited[i] = true;
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                for (int next : adj[node]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        reach[i][next] = true;
                        q.push(next);
                    }
                }
            }
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            result.push_back(reach[query[0]][query[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 a, b in prerequisites:
            adj[a].append(b)
        
        reach = [[False] * numCourses for _ in range(numCourses)]
        for i in range(numCourses):
            visited = [False] * numCourses
            visited[i] = True
            queue = deque([i])
            while queue:
                node = queue.popleft()
                for next_node in adj[node]:
                    if not visited[next_node]:
                        visited[next_node] = True
                        reach[i][next_node] = True
                        queue.append(next_node)
        
        return [reach[u][v] for u, v in queries]

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[][] reach = new boolean[numCourses][numCourses];
        for (int i = 0; i < numCourses; i++) {
            boolean[] visited = new boolean[numCourses];
            visited[i] = true;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : adj.get(node)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        reach[i][next] = true;
                        queue.offer(next);
                    }
                }
            }
        }
        
        List<Boolean> result = new ArrayList<>();
        for (int[] q : queries) {
            result.add(reach[q[0]][q[1]]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(V × (V + E) + q)

We run BFS from each of the V nodes. Each BFS visits at most V nodes and traverses at most E edges, costing O(V + E). With V BFS runs, the preprocessing is O(V × (V + E)). After preprocessing, each of the q queries is answered in O(1) by a matrix lookup.

For this problem: V ≤ 100 and E ≤ ~5,000, so preprocessing is at most 100 × 5,100 ≈ 510,000 operations. The q ≤ 10^4 queries add only 10,000 O(1) lookups.

Space Complexity: O(V²)

The V×V reachability matrix dominates storage. The adjacency list uses O(V + E) and each BFS uses a visited array of size V, but these are smaller than V².

Why This Approach Is Not Efficient

BFS precomputation is a major improvement over the brute force — it eliminates all redundant traversals by doing the work upfront. However, its implementation requires managing several moving parts: an adjacency list, V separate BFS runs each with their own queue and visited array, and careful bookkeeping to avoid revisiting nodes.

For dense prerequisite graphs where the number of edges E approaches V × (V-1)/2, the O(V × (V + E)) preprocessing becomes O(V³), the same worst-case as Floyd-Warshall. Yet Floyd-Warshall achieves this with dramatically simpler code: just three nested for-loops and a single boolean condition. No queues, no visited arrays, no adjacency list — it operates directly on the reachability matrix.

Floyd-Warshall's regular, predictable memory access pattern (iterating through a 2D array in order) also tends to perform better in practice due to CPU cache efficiency. For this problem's constraints (V ≤ 100), both approaches are fast, but Floyd-Warshall is the standard, cleaner solution for computing transitive closure.

Optimal Approach - Floyd-Warshall Transitive Closure

Intuition

Floyd-Warshall is a classic algorithm for finding shortest paths between all pairs of nodes in a graph. Here, we adapt it for transitive closure: determining whether a path exists between every pair of nodes (regardless of length).

The core idea is strikingly simple. We maintain a boolean matrix reach[i][j] that says whether course i can reach course j. Initially, only direct prerequisites are marked true. Then we ask a single powerful question for every possible intermediate course k:

"If course i can already reach course k, and course k can already reach course j, then course i can also reach course j."

By systematically checking every possible intermediate course k (from 0 to V-1), we gradually discover all indirect relationships. The algorithm builds upon its own discoveries — a path found using intermediate k=1 can later be extended through intermediate k=2.

Imagine a postal system: initially, each post office only knows its direct delivery routes. The Floyd-Warshall algorithm introduces relay stations one by one. Each time a new relay is added, every post office checks: "Can I send mail through this relay to reach destinations I couldn't before?" After considering all relays, every post office knows its complete delivery network.

Step-by-Step Explanation

Let's trace Floyd-Warshall on a 4-course chain to see how it discovers indirect prerequisites:

numCourses = 4, prerequisites = [[0,1],[1,2],[2,3]], queries = [[0,3],[3,0]].

Step 1: Initialize a 4×4 matrix. Mark direct prerequisites:

reach[0][1] = true (0 is prerequisite of 1)
reach[1][2] = true (1 is prerequisite of 2)
reach[2][3] = true (2 is prerequisite of 3)

Step 2: k=0 — Consider course 0 as an intermediate relay. For any pair (i,j), check: can i reach 0 AND can 0 reach j? No course is a prerequisite of course 0 (nothing points to 0), so no new paths through relay 0.

Step 3: k=1 — Consider course 1 as intermediate. Who can reach 1? Course 0 can (reach[0][1]=true). What can 1 reach? Course 2 (reach[1][2]=true). Discovery: reach[0][1]=true AND reach[1][2]=true → set reach[0][2]=true. Course 0 can now reach course 2 through chain 0→1→2.

Step 4: k=2 — Consider course 2 as intermediate. Who can reach 2? Courses 0 (just discovered!) and 1 (direct). What can 2 reach? Course 3 (reach[2][3]=true). Two discoveries:

reach[0][2]=true AND reach[2][3]=true → set reach[0][3]=true (chain 0→1→2→3)
reach[1][2]=true AND reach[2][3]=true → set reach[1][3]=true (chain 1→2→3)

Step 5: k=3 — Consider course 3 as intermediate. Course 3 has no outgoing prerequisites (row 3 is all false). No new paths.

Step 6: Transitive closure complete. From 3 direct prerequisites, we discovered 3 indirect ones (0→2, 0→3, 1→3). Answer queries:

[0,3]: reach[0][3]=true → true
[3,0]: reach[3][0]=false → false
Result: [true, false]

Floyd-Warshall — Building the Transitive Closure Matrix — Watch as the algorithm considers each course as an intermediate relay, progressively discovering indirect prerequisite chains hidden in the graph.

Algorithm

Create a V×V boolean matrix reach, initialized to all false
For each prerequisite [a, b], set reach[a][b] = true (mark direct prerequisites)
For each intermediate course k from 0 to V-1:
- For each source course i from 0 to V-1:
  - For each destination course j from 0 to V-1:
    - If reach[i][k] is true AND reach[k][j] is true, set reach[i][j] = true
For each query [u, v], return reach[u][v]

Critical: The loop over k MUST be the outermost loop. This ensures that when we use course k as a relay, all shorter relay chains (using courses 0 through k-1) have already been computed.

Code

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& p : prerequisites) {
            reach[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++) {
                    if (reach[i][k] && reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }
        
        vector<bool> result;
        for (auto& q : queries) {
            result.push_back(reach[q[0]][q[1]]);
        }
        return result;
    }
};

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: list[list[int]], queries: list[list[int]]) -> list[bool]:
        reach = [[False] * numCourses for _ in range(numCourses)]
        
        for a, b in prerequisites:
            reach[a][b] = 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 List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[numCourses][numCourses];
        
        for (int[] p : prerequisites) {
            reach[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++) {
                    if (reach[i][k] && reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }
        
        List<Boolean> result = new ArrayList<>();
        for (int[] q : queries) {
            result.add(reach[q[0]][q[1]]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(V³ + q)

The three nested loops (k, i, j) each iterate V times, giving V³ total iterations. Inside the innermost loop, we perform a constant-time boolean check and assignment. With V ≤ 100, this is 100³ = 1,000,000 operations — extremely fast.

After preprocessing, each of the q queries is a single O(1) matrix lookup. So the total is O(V³ + q).

Space Complexity: O(V²)

The V×V boolean reachability matrix requires V² space. With V ≤ 100, this is just 10,000 booleans (approximately 10 KB). No adjacency list is needed — we operate directly on the matrix.

Compared to the brute force (O(q × (V + E)) time), Floyd-Warshall decouples the cost from the number of queries. Whether you have 1 query or 10,000, the preprocessing cost is the same. This makes it ideal when the number of queries is large relative to the graph size.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Course Schedule IV

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - BFS Precomputation

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Floyd-Warshall Transitive Closure

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis