Course Schedule IV

Medium
945.

Course Schedule IV

Course Schedule IV is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @param {number[][]} queries
 * @return {number[]}
 */
var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Course Schedule IV — Solution in Python, Java & C++

Course Schedule IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Course Schedule IV is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Adobe interviews.

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

Hints for Course Schedule IV

  1. Hint 1

    The queries ask about reachability, not direct edges.

  2. Hint 2

    With at most 100 courses, the whole reachability matrix fits easily.

  3. Hint 3

    Compute the transitive closure once, then answer every query in O(1).

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]

Java

public static int[] 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++) {
            if (!reach[i][k]) continue;
            for (int j = 0; j < numCourses; j++) {
                if (reach[k][j]) reach[i][j] = true;
            }
        }
    }
    int[] out = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        out[i] = reach[queries[i][0]][queries[i][1]] ? 1 : 0;
    }
    return out;
}

C++

vector<int> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
    vector<vector<char>> reach(numCourses, vector<char>(numCourses, 0));
    for (auto& p : prerequisites) reach[p[0]][p[1]] = 1;
    for (int k = 0; k < numCourses; k++) {
        for (int i = 0; i < numCourses; i++) {
            if (!reach[i][k]) continue;
            for (int j = 0; j < numCourses; j++) {
                if (reach[k][j]) reach[i][j] = 1;
            }
        }
    }
    vector<int> out;
    for (auto& q : queries) out.push_back(reach[q[0]][q[1]] ? 1 : 0);
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)