Leetcode 1462. Course Schedule IV

Problem

Leetcode 1462 - Course Schedule IV

Example:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: 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.

Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites, and each course is independent.

Approach

First we can create a hash map for all the courses and its prerequisite course. Once this is done we can run a DFS to find all the prerequisites. Meaning if our example was [[1,2], [2,3]] then with DFS we can see that for someone to take course 3, we must take course 1.

We can make this as our new list for req[c]. Once we run a DFS on every numCourse, we can then find if course $u$ is required for course $v$ by checking the hash map

Here is the Python code for the solution:

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        req = {i: [] for i in range(numCourses)}
        res = []

        for p, c in prerequisites:
            req[c].append(p)

        def dfs(c):
            if c in visited:
                return

            visited.add(c)
            for p in req[c]:
                dfs(p)
    
        for i in range(numCourses):
            visited = set()
            dfs(i)
            visited.remove(i)
            req[i] = list(visited)
        
        for u, v in queries:
            res.append(u in req[v])
        return res     

Time Complexity and Space Complexity

Time Complexity: $O(V+E)$

Space Complexity: $O(V+E)$