1462. Course Schedule IV - Explanation

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

Example 1:

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

Output: [false,true]

Example 2:

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

Output: [false]

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 <= 10,000
0 <= ui, vi <= numCourses - 1
ui != vi

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force (DFS)

Intuition

To check if course A is a prerequisite of course B, we need to determine if there is a path from A to B in the prerequisite graph. A depth-first search starting from A can explore all courses reachable from A. If we reach B during this traversal, then A is indeed a prerequisite of B.

Algorithm

Build an adjacency list from the prerequisites, where each course points to its direct successors.
For each query (u, v), run a DFS starting from u.
In the DFS, if we reach v, return true.
Otherwise, recursively explore all neighbors and return true if any path reaches v.
If no path is found, 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 u, v in prerequisites:
            adj[u].append(v)

        def dfs(node, target):
            if node == target:
                return True
            for nei in adj[node]:
                if dfs(nei, target):
                    return True
            return False

        res = []
        for u, v in queries:
            res.append(dfs(u, v))
        return res

Time & Space Complexity

Time complexity: $O((V + E) * m)$
Space complexity: $O(V + E + m)$

Where $m$ is the number of queries, $V$ is the number of courses, and $E$ is the number of prerequisites.

2. Depth First Search (Hash Set)

Intuition

Instead of running DFS for every query, we can precompute all prerequisites for each course. For each course, we use DFS to find all courses that are prerequisites (directly or indirectly) and store them in a set. Then answering any query becomes a simple set lookup.

Algorithm

Build an adjacency list where each course points to its direct prerequisites.
For each course, run DFS to collect all reachable prerequisites into a set.
Cache these sets to avoid recomputation.
Each course's prerequisite set includes itself and all prerequisites of its direct prerequisites.
For each query (u, v), check if u is in the prerequisite set of v.

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        adj = defaultdict(list)
        for prereq, crs in prerequisites:
            adj[crs].append(prereq)

        def dfs(crs):
            if crs not in prereqMap:
                prereqMap[crs] = set()
                for prereq in adj[crs]:
                    prereqMap[crs] |= dfs(prereq)
                prereqMap[crs].add(crs)
            return prereqMap[crs]

        prereqMap = {}
        for crs in range(numCourses):
            dfs(crs)

        res = []
        for u, v in queries:
            res.append(u in prereqMap[v])
        return res

Time & Space Complexity

Time complexity: $O(V * (V + E) + m)$
Space complexity: $O(V ^ 2 + E + m)$

Where $m$ is the number of queries, $V$ is the number of courses, and $E$ is the number of prerequisites.

3. Depth First Search (Memoization)

Intuition

We can optimize by memoizing the result for each pair of courses. When checking if course A is a prerequisite of course B, we store the result so that future queries for the same pair can be answered instantly. This avoids redundant graph traversals for repeated or similar queries.

Algorithm

Build an adjacency list where each course points to its direct prerequisites.
Create a 2D memoization array initialized to -1 (unknown).
For each query (u, v), run DFS to check if u is a prerequisite of v.
During DFS, if the result for (course, prereq) is already computed, return it.
Otherwise, check all direct prerequisites. If any of them is the target or leads to the target, mark and return true.
If no path exists, mark and return false.

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        adj = [[] for _ in range(numCourses)]
        isPrereq = [[-1] * numCourses for _ in range(numCourses)]
        for prereq, crs in prerequisites:
            adj[crs].append(prereq)
            isPrereq[crs][prereq] = True

        def dfs(crs, prereq):
            if isPrereq[crs][prereq] != -1:
                return isPrereq[crs][prereq] == 1

            for pre in adj[crs]:
                if pre == prereq or dfs(pre, prereq):
                    isPrereq[crs][prereq] = 1
                    return True

            isPrereq[crs][prereq] = 0
            return False

        res = []
        for u, v in queries:
            res.append(dfs(v, u))
        return res

Time & Space Complexity

Time complexity: $O(V * (V + E) + m)$
Space complexity: $O(V ^ 2 + E + m)$

Where $m$ is the number of queries, $V$ is the number of courses, and $E$ is the number of prerequisites.

4. Topological Sort (Kahn's Algorithm)

Intuition

Using topological sort, we process courses in an order where all prerequisites of a course are processed before the course itself. When we process a course, we propagate all its prerequisites to its successors. This way, each course accumulates the complete set of all courses that must be taken before it.

Algorithm

Build an adjacency list and compute the indegree for each course.
Initialize a queue with all courses having indegree 0.
For each course processed:
- For each successor, add the current course and all its prerequisites to the successor's prerequisite set.
- Decrement the successor's indegree and add to queue if it becomes 0.
After processing all courses, each course has a complete set of its prerequisites.
For each query (u, v), check if u is in the prerequisite set of v.

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        adj = [set() for _ in range(numCourses)]
        indegree = [0] * numCourses
        isPrereq = [set() for _ in range(numCourses)]

        for pre, crs in prerequisites:
            adj[pre].add(crs)
            indegree[crs] += 1

        q = deque([i for i in range(numCourses) if indegree[i] == 0])

        while q:
            node = q.popleft()
            for neighbor in adj[node]:
                isPrereq[neighbor].add(node)
                isPrereq[neighbor].update(isPrereq[node])
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)

        return [u in isPrereq[v] for u, v in queries]

Time & Space Complexity

Time complexity: $O(V * (V + E) + m)$
Space complexity: $O(V ^ 2 + E + m)$

Where $m$ is the number of queries, $V$ is the number of courses, and $E$ is the number of prerequisites.

5. Floyd Warshall Algorithm

Intuition

The Floyd-Warshall algorithm finds all-pairs reachability in a graph. We can adapt it to find transitive closure: if there is a path from A to B through any intermediate course K, then A is a prerequisite of B. After running the algorithm, we have direct O(1) lookup for any pair.

Algorithm

Create a 2D boolean matrix initialized to false.
Mark direct prerequisites as true in the matrix.
For each intermediate course k, iterate through all pairs (i, j).
If there is a path from i to k and from k to j, mark the path from i to j as true.
For each query (u, v), simply return the value at matrix[u][v].

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        res = []
        adj = [[False] * numCourses for _ in range(numCourses)]

        for pre, crs in prerequisites:
            adj[pre][crs] = True

        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    adj[i][j] = adj[i][j] or (adj[i][k] and adj[k][j])

        for u, v in queries:
            res.append(adj[u][v])

        return res

Time & Space Complexity

Time complexity: $O(V ^ 3 + E + m)$
Space complexity: $O(V ^ 2 + E + m)$

Where $m$ is the number of queries, $V$ is the number of courses, and $E$ is the number of prerequisites.

Common Pitfalls

Confusing Edge Direction

A common mistake is building the graph with edges pointing in the wrong direction. The prerequisite [a, b] means course a must be taken before course b, so a -> b. Reversing this leads to incorrect reachability results.

# Wrong: edge points from course to prerequisite
for pre, crs in prerequisites:
    adj[crs].append(pre)  # Incorrect for "is a prerequisite of" queries

# Correct: edge points from prerequisite to course
for pre, crs in prerequisites:
    adj[pre].append(crs)  # Now adj[u] contains courses that u is a prerequisite of

Rerunning DFS for Every Query Without Memoization

Running a fresh DFS for each query without caching results leads to repeated work. With many queries, this causes TLE. Always memoize visited pairs or precompute the full transitive closure.

# Inefficient: no memoization
def dfs(node, target):
    if node == target:
        return True
    for nei in adj[node]:
        if dfs(nei, target):
            return True
    return False

# Each query starts from scratch - O(V+E) per query

Not Handling Disconnected Nodes

Courses with no prerequisites and no dependents are still valid nodes. Forgetting to initialize them in your adjacency list or prerequisite map causes KeyError or incorrect results when they appear in queries.