MediumDepth-First SearchBreadth-First SearchGraphTopological SortMatrix

Course Schedule IV

1 approach, code in every language

You are given an integer numCourses representing the courses labeled from 0 to numCourses - 1, together with a list of prerequisites where each pair [a, b] means course a must be taken before course b. A course x is a prerequisite of course y if x appears directly before y, or if x is a prerequisite of some course z that is itself a prerequisite of y. In other words, the prerequisite relation is transitive.

You are also given a list of queries where each query [u, v] asks whether course u is a prerequisite (directly or indirectly) of course v. Return a boolean array whose i-th entry answers the i-th query.

The graph of courses is guaranteed to have no cycles, so a consistent ordering of the courses always exists.

Example 1

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

Output: [true,false]

0 leads to 1 and 1 leads to 2, so 0 is an indirect prerequisite of 2 (true). There is no path from 2 back to 0, so the second answer is false.

Example 2

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

Output: [false,false]

With no prerequisite edges, neither course can be reached from the other, so both queries are false.

Constraints

2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1)) / 2
prerequisites[i].length == 2
0 <= a, b < numCourses
a != b, and all prerequisite pairs are unique
The prerequisite graph is a DAG (no cycles)
1 <= queries.length <= 10^4
queries[i].length == 2
0 <= u, v < numCourses

Transitive Closure (Floyd-Warshall OR propagation)

Precompute a reachable[u][v] matrix that marks every prerequisite relationship, then answer each query in O(1).

Loading animation…

Intuition

A query asks whether one course can be reached from another by following prerequisite edges, so the core object we need is reachability between every pair of courses. Since numCourses is at most 100, we can afford a full n-by-n boolean matrix that records whether i reaches j. We seed the matrix with the direct edges, then repeatedly propagate: if i reaches k and k reaches j, then i reaches j. This is exactly the Floyd-Warshall idea applied to boolean OR instead of shortest paths. Once the closure is complete, each of the possibly many queries is a single matrix lookup.

Algorithm walkthrough

1Allocate an n-by-n boolean matrix reachable, initialized to false.
2For every prerequisite [a, b], set reachable[a][b] = true to record the direct edges.
3Run three nested loops over intermediate node k, source i, and destination j; whenever reachable[i][k] and reachable[k][j] are both true, mark reachable[i][j] = true.
4After the triple loop, reachable[u][v] is true exactly when u is a prerequisite of v, directly or indirectly.
5For each query [u, v], append reachable[u][v] to the answer.
6Return the collected boolean array.

Implementation

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        reachable = [[False] * numCourses for _ in range(numCourses)]
        for u, v in prerequisites:
            reachable[u][v] = True
        for k in range(numCourses):
            for i in range(numCourses):
                if reachable[i][k]:
                    for j in range(numCourses):
                        if reachable[k][j]:
                            reachable[i][j] = True
        return [reachable[u][v] for u, v in queries]

Time

O(n^3 + q)

Space

O(n^2)

n is numCourses and q is the number of queries. Building the closure dominates at O(n^3); each query is O(1). The matrix uses O(n^2) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Which Modules Must Come First is our own problem on the technique behind Course Schedule IV: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free