Today’s problem

https://leetcode.com/problems/course-schedule-iv/description/

Intuition

In this problem, we need to find whether a point is the father of another point or not. In this case, we can simply use one set to store all the fathers of a point and path that set to all its children.

Approach

  • Use a dfs to iterate all the points.
  • Create a set for every point, then pass it to its children.

Complexity

  • Time complexity: $O(N^3 + Q)$. We would at visit each edge at most once. The passing of a set is $O(N)$. So the final time complexity would be $O(N^3 + Q)$.

  • Space complexity: $O(N^2) + Q$. We need to store a set for every point and we also need to store the answer.

Code

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        edges = [[] for _ in range(numCourses)]
        prereq = [set([_]) for _ in range(numCourses)]

        for x, y in prerequisites:
            edges[y].append(x)
        
        def dfs(x):
            for to in edges[x]:
                if len(prereq[to]) == 1:
                    dfs(to)
                prereq[x] = prereq[x] | prereq[to]

        for i in range(numCourses):
            dfs(i)
        
        ans = []
        for x, y in queries:
            if x in prereq[y]:
                ans.append(True)
            else:
                ans.append(False)
        
        return ans