#1462

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Course Schedule IV

Determine if one course is a prerequisite of another using graph indegree tracking and topological ordering efficiently.

depth first search breadth first search graph topological sort

Problem Statement

You are given a total of numCourses courses labeled from 0 to numCourses - 1. Each element in prerequisites is a pair [ai, bi], indicating that course ai must be completed before course bi. You need to process multiple queries to check if one course is a prerequisite of another.

Prerequisites can be indirect, meaning if course a is required before b, and b before c, then a is indirectly required before c. Given an array queries of pairs [uj, vj], determine for each query whether course uj is a prerequisite of course vj, considering both direct and indirect prerequisites.

Examples

Example 1

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

Output: [false,true]

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]

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]

Example details omitted.

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

Solution Approach

Build a Graph and Track Indegree

Create an adjacency list for all courses and an indegree array. Courses with indegree zero can be processed first. This setup mirrors topological sort preparation and ensures we correctly propagate prerequisite relationships.

Compute Reachability via Topological Ordering

Use a queue to process courses in topological order. For each course, mark all reachable courses in a matrix isReachable[i][j]. This ensures indirect prerequisites are accounted for, and each query can later be answered in O(1) time.

Answer Queries Using the Reachability Matrix

Iterate through queries and check isReachable[uj][vj] for each pair. Using the precomputed reachability matrix ensures constant time lookups, avoiding repeated DFS or BFS for each query, which prevents TLE in dense graphs.

Complexity Analysis

Metric	Value
Time	O(N^3 + Q)
Space	O(N^2)

Time complexity is O(N^3 + Q) because building the reachability matrix involves O(N^3) operations for N courses, and answering Q queries is O(Q). Space complexity is O(N^2) to store the reachability matrix.

What Interviewers Usually Probe

Are you considering both direct and indirect prerequisites?
Can you optimize repeated queries without running DFS each time?
How does topological ordering simplify the prerequisite propagation?

Common Pitfalls or Variants

Common pitfalls

Ignoring indirect prerequisites leads to incorrect query answers.
Attempting DFS/BFS per query may exceed time limits on large inputs.
Failing to initialize or update the reachability matrix correctly during topological processing.

Follow-up variants

Check if all courses can be completed given the same prerequisites graph.
Determine the minimum number of courses required to satisfy a set of query constraints.
Compute the longest chain of prerequisites instead of answering individual queries.

FAQ

What pattern does Course Schedule IV follow?

It follows a graph indegree plus topological ordering pattern, where building a reachability matrix lets us answer all queries efficiently.

Can DFS alone solve Course Schedule IV?

DFS can identify reachability but may be inefficient per query; topological ordering with an isReachable matrix handles multiple queries faster.

Why do we need a reachability matrix?

It precomputes direct and indirect prerequisites so each query can be answered in constant time, avoiding repeated graph traversal.

What are the main pitfalls in solving Course Schedule IV?

Common mistakes include ignoring indirect prerequisites, running DFS per query, and incorrectly updating reachability during topological processing.

How do topological sort and indegree tracking help here?

They ensure courses are processed in prerequisite order, propagating reachability correctly and efficiently without revisiting nodes unnecessarily.

terminal

Solution

Solution 1: Floyd's Algorithm

We create a 2D array $f$, where $f[i][j]$ indicates whether node $i$ can reach node $j$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def checkIfPrerequisite(
        self, n: int, prerequisites: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        f = [[False] * n for _ in range(n)]
        for a, b in prerequisites:
            f[a][b] = True
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if f[i][k] and f[k][j]:
                        f[i][j] = True
        return [f[a][b] for a, b in queries]

Solution 2: Topological Sorting

Similar to Solution 1, we create a 2D array $f$, where $f[i][j]$ indicates whether node $i$ can reach node $j$. Additionally, we create an adjacency list $g$, where $g[i]$ represents all successor nodes of node $i$, and an array $indeg$, where $indeg[i]$ represents the in-degree of node $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def checkIfPrerequisite(
        self, n: int, prerequisites: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        f = [[False] * n for _ in range(n)]
        for a, b in prerequisites:
            f[a][b] = True
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if f[i][k] and f[k][j]:
                        f[i][j] = True
        return [f[a][b] for a, b in queries]

Continue Practicing

#1203 sort items by groups respecting dependencies #802 find eventual safe states #2328 number of increasing paths in a grid