Get started

Course Schedule IV — Medium Problem & Solution

numCourses courses are numbered 0 … numCourses - 1, and prerequisites[i] = [a, b] means a must be taken before b.

Problem statement

numCourses courses are numbered 0 … numCourses - 1, and prerequisites[i] = [a, b] means a must be taken before b.

Prerequisites are transitive: if a comes before b and b before c, then a comes before c. For each queries[j] = [u, v], answer 1 if u is a prerequisite of v and 0 otherwise.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [0,1]
Explanation: Course 1 comes before course 0, not the other way round.

Example 2

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [0,0]
Explanation: No prerequisites at all.

Example 3

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

Constraints

  • 2 <= numCourses <= 100
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1) / 2
  • prerequisites[i].length == 2
  • 0 <= a, b < numCourses
  • a != b
  • All the pairs of prerequisites are unique.
  • The prerequisites graph has no cycles.
  • 1 <= queries.length <= 10^4
  • 0 <= u, v < numCourses
  • u != v

How to solve Course Schedule IV

Build the numCourses × numCourses reachability matrix once with a Floyd–Warshall-style triple loop, then each query is a single lookup.

Approach

  1. Seed reach[a][b] = true for every direct prerequisite.
  2. For each intermediate k, if i reaches k and k reaches j, mark i reaches j.
  3. Answer each query from the matrix.

Why it works

With numCourses <= 100 the closure is only 10^6 boolean updates, while there may be 10^4 queries — so precomputing once beats a search per query by a wide margin. The k loop must be outermost: that is what lets paths through several intermediates build up, one hop at a time.

Complexity

  • Time — O(numCourses³ + queries)
  • Space — O(numCourses²)

Pitfalls

  • Checking only direct edges misses every transitive prerequisite.
  • The k loop must be the outer one; reordering breaks the closure.
  • The relation is directed: reach[u][v] and reach[v][u] are different questions.

Reference solution

Python

from typing import List

def checkIfPrerequisite(numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[int]:
    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):
            if not reach[i][k]:
                continue
            for j in range(numCourses):
                if reach[k][j]:
                    reach[i][j] = True
    return [1 if reach[u][v] else 0 for u, v in queries]

JavaScript

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    var i, j, k;
    var reach = [];
    for (i = 0; i < numCourses; i++) {
        var row = [];
        for (j = 0; j < numCourses; j++) row.push(false);
        reach.push(row);
    }
    for (i = 0; i < prerequisites.length; i++) {
        reach[prerequisites[i][0]][prerequisites[i][1]] = true;
    }
    for (k = 0; k < numCourses; k++) {
        for (i = 0; i < numCourses; i++) {
            if (!reach[i][k]) continue;
            for (j = 0; j < numCourses; j++) {
                if (reach[k][j]) reach[i][j] = true;
            }
        }
    }
    var out = [];
    for (i = 0; i < queries.length; i++) {
        out.push(reach[queries[i][0]][queries[i][1]] ? 1 : 0);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue