NeetCode #578LC-1462MediumGraphsNC 250
← Back to All Problems#578 · #1462 · Course Schedule IV(课程表 IV)
📌 Problem Statement & Constraints
There are
numCourses courses. Given prerequisites and queries where queries[i] = [a, b], return a boolean array where the i-th entry says whether a is a prerequisite of b. Constraints: 2 <= numCourses <= 100, 0 <= prerequisites.length <= numCourses * (numCourses - 1) / 2, 1 <= queries.length <= 10^4.💡 Core Algorithmic Approaches
- Compute the transitive closure of the prerequisite relation.
reach[i]is the set of courses reachable fromi(i.e. courses that requireitransitively).- A DFS from each node builds the sets; with
numCourses <= 100this is cheap. - Each query is then a set membership test.
💻 Benchmark Python3 Implementation
class Solution:
def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
from collections import defaultdict
g = defaultdict(list)
for a, b in prerequisites: # a must precede b -> edge a -> b
g[a].append(b)
reach = [set() for _ in range(numCourses)]
def dfs(node: int) -> set:
if reach[node]:
return reach[node] # memoised
for nxt in g[node]:
reach[node].add(nxt)
reach[node] |= dfs(nxt) # transitive
return reach[node]
for i in range(numCourses):
dfs(i)
return [b in reach[a] for a, b in queries]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V * (V + E)) for the DFS with set unions; each query is O(1).
💾 Space Complexity
O(V^2) for the transitive-closure sets.
⚠️ Interview Pitfalls & Follow-ups
- Checking only the direct prerequisites: the relation is transitive.
- Not memoising the DFS: the same subtrees would be recomputed many times.
- Confusing the direction:
[a, b]meansais a prerequisite ofb, so the edge isa -> b. - Using a Floyd-Warshall style matrix: also O(V^3) and workable here, but the set-based closure is simpler to reason about.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.