Course Schedule IV - Leetcode 1462 - Python

[@okoyemoses9019]

I find Kahn's Algorithm and BFS approaches a lot more straight forward for these kind of problems.

[@pushpavathikn8314]

Solved if by myself after understanding the concept from course schedule 2, Thanks NC !! 😅

[@sergiofranklin8809]

can you write your solution? I want to see how it's related with course_schedule 2

[@pushpavathikn8314]

@ ignore the print statements class Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: preq = {i:[] for i in range(numCourses)} ans = [] indirect_preq = {i: set() for i in range(numCourses)} for pre_req, crs in prerequisites: preq[crs].append(pre_req) visit = set() def dfs(crs): if preq[crs] == []: indirect_preq[crs].add(crs) return indirect_preq[crs] if crs in visit: return indirect_preq[crs] for c in preq[crs]: reqs = dfs(c) indirect_preq[crs].update(reqs) visit.add(crs) indirect_preq[crs].add(crs) return indirect_preq[crs] for c in range(numCourses): dfs(c) print(indirect_preq.keys()) print(indirect_preq.values()) for q in queries: if q[0] in indirect_preq.get(q[1]): ans.append(True) else: ans.append(False) return ans

[@pushpavathikn8314]

class Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: preq = {i:[] for i in range(numCourses)} ans = [] indirect_preq = {i: set() for i in range(numCourses)} for pre_req, crs in prerequisites: preq[crs].append(pre_req) visit = set() def dfs(crs): if preq[crs] == []: indirect_preq[crs].add(crs) return indirect_preq[crs] if crs in visit: return indirect_preq[crs] for c in preq[crs]: reqs = dfs(c) indirect_preq[crs].update(reqs) visit.add(crs) indirect_preq[crs].add(crs) return indirect_preq[crs] for c in range(numCourses): dfs(c) print(indirect_preq.keys()) print(indirect_preq.values()) for q in queries: if q[0] in indirect_preq.get(q[1]): ans.append(True) else: ans.append(False) return ans

[@kamila5207]

hey @NeetCodeIO, you ordering pairs in prerequisites from right to left, but in explanation of this task on Leetcode there are direction from left to right, is it mistake of Leetcode platform or yours?

[@paras9392]

Here neetcode's explanation A -> B does not indicate that A is a prerequisite of B (like what this notation meant e.g. in course schedule I and II problem) instead the arrow here indicates all the nodes which are (direct) prerequisites of A. So here we are analyzing the inverted relationship i.e. instead of looking for all the nodes which are prerequisite of a node, we are looking for all the direct prerequisite nodes of a particular node .

[@yang5843]

class Solution { Map set = new HashMap(); public List checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) { List list = new ArrayList(); Map map = new HashMap(); for (int i=0;i

[@chair_smesh]

Is there a method to which new problems you upload? Or do you just upload whatever problem you’re practicing at the time?

[@shavvasatya7131]

Daily Leetcode Problems.

[@yang5843]

Today's problem can be found here: kzbin.info/www/bejne/gV61iq16j9Cteas

[@ray811030]

Once you use hashmap to store what nodes that current node can reach, time complexity of running DFS can be O(N+E) instead O(N(N+E))?

[@sambro890]

Hey NeetCode … you know what? You are the best…

[@sonicjetson6253]

chaatu

[@iamnoob7593]

thanks man

[@cooltomcatty]

I have been following these course schedule problems but one thing i didn't understand is how is the time complexity O(P+N)?? Can someone explain??

[@theJasin]

You’re only visiting the nodes and edges once which makes it O(V+E)

[@monicawang8447]

What's the space complexity? Is it the same as the time complexity?

[@cosepeter2197]

Hey Neet, can you make video on how to stay ahead with rise of AI as a programmer?

[@theJasin]

I think Kahns is more straightforward

[@cocodinary]

Help: looking for solution of leetcode 1203: sort-items-by-groups-respecting-dependencies

[@piglovesasy]

Where is Course Schedule III? can you please do one soon :)

[@aaditya_87]

can we use union find ?

[@bluesteel1]

You cannot use union find in directed graphs

[@wallyyu5426]

made it so easy

[@wallyyu5426]

interviewing amazon intern tomorrow, this video will help me get that offer!