⚡Flashcard Drill➔
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

  1. Compute the transitive closure of the prerequisite relation.
  2. reach[i] is the set of courses reachable from i (i.e. courses that require i transitively).
  3. A DFS from each node builds the sets; with numCourses <= 100 this is cheap.
  4. 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] means a is a prerequisite of b, so the edge is a -> 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems