1462. Course Schedule IV

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/course-schedule-iv
• topics: Graph

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.

Idea

• Inverse dependencies + Recursion with cache. Slow but simple
• Kahn’s algorithm + bitmasks. Fast

Code

Recursion

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        pre = defaultdict(set)
        for x in prerequisites:
            pre[x[1]].add(x[0])
 
        @cache
        def check(i, j):
            if j in pre[i]:
                return True
            for t in pre[i]:
                if check(t, j):
                    return True
            return False
        
        return [check(q[1], q[0]) for q in queries]

Kahn’s algorithm + bitmasks

from collections import deque
 
class Solution(object):
    def checkIfPrerequisite(self, numCourses, prerequisites, queries):
        adj = [[] for _ in range(numCourses)]
        prereq = [0] * numCourses  # Bitmask for prerequisites
        in_degree = [0] * numCourses
        
        # Build graph and initialize direct prerequisites
        for a, b in prerequisites:
            adj[a].append(b)
            prereq[b] |= 1 << a  # Set the a-th bit for course b
            in_degree[b] += 1
        
        # Topological sort using Kahn's algorithm
        q = deque()
        for i in range(numCourses):
            if in_degree[i] == 0:
                q.append(i)
        
        while q:
            u = q.popleft()
            for v in adj[u]:
                prereq[v] |= prereq[u]  # Merge u's prerequisites into v's
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    q.append(v)
        
        # Answer queries using bitmask checks
        ans = []
        for u, v in queries:
            ans.append((prereq[v] & (1 << u)) != 0)
        return ans