Find Eventual Safe States - Leetcode 802 - Python

[@amegahed94]

This is a super neat solution. Initially, I was approaching this with a visited and current_path sets & was doing backtracking on both :) Now the code is much cleaner! Thank you for this video.

[@joelpww]

4 has an outgoing edge

[@awekeningbro1207]

and

[@vivekgagrani8288]

So 4 should not be a terminal node Isn't it

[@_7__716]

But it leads to a terminal node which makes it a safe node

[@vivekgagrani8288]

@@_7__716 yes agree, but in video during explanation, he said 4 is a terminal node.

[@river.]

@@vivekgagrani8288 bhawnao ko samjho

[@tommysohn2747]

such a elegant way to detect loops

[@sidazhong2019]

This problem is genius. Usually, we use a visited set() in such graph problems to detect a circle. But not for this question. A visited node may visit a second time since one node connects to many nodes. So, it uses a hashmap instead of the visited set! The default set value to False. Once the node reaches the end, it changes to True. Damn it, I didn't come up with it.

[@Sulerhy]

Same here bro, thank you

[@juhairahamed5342]

Good Explanation. Get new way of thinking

[@CineVibe69]

This is Superbb.. Very clean solution

[@rithickchowdhury7116]

Thanks for making this super easy 🙌

[@AlancRodriguez]

A genius can make a complex topic seem simple

[@mehulsolanki9435]

This is illegal. You can't make a problem sound soo simple !!

[@Man_of_Culture.]

Solution optimized with dp (safe vector used as dp) concept class Solution { public: bool dfs(int u,vector&visited,vector&safe,vector& graph) { visited[u]=1; bool isSafe=1; for(auto v:graph[u]) { if(visited[v]) isSafe&=safe[v]; else isSafe&=dfs(v,visited,safe,graph); } return safe[u]=isSafe; } vector eventualSafeNodes(vector& graph) { int n=graph.size(); vectorvisited(n,0),safe(n,0); for(int i=0;i

[@nishantingle1438]

Variation of Topological Sort

[@halahmilksheikh]

Yeah it's a modification of topological sort. Basically asking to find nodes that aren't part of a cycle. Here's a solution that uses topo sort DFS using a white gray black implementation. It's also O(V+E) uses the same visited each dfs call. /** * @param {number[][]} graph * @return {number[]} */ var eventualSafeNodes = function(graph) { let visited = new Array(graph.length).fill(0) let res = [] for (let i = 0; i < graph.length; i++) { if (dfs(i)) { res.push(i) } } return res // return true if not part of a cycle // false if part of cycle function dfs(i) { if (visited[i] == 1) { return false } if (visited[i] == 2) { return true } visited[i] = 1 for (let nei of graph[i]) { if (dfs(nei) == false) { return false } } visited[i] = 2 return true } };

[@alexthezhang]

Thank you!!!

[@vineethnc8934]

Please solve Leetcode 321..

[@schan263]

I just finished this question but my implementation is not as clean as yours.

[@tommasodonato991]

No algoexpert, for the 1000th time, i don’t want to be a software engineer at google. Thank you

[@a4addel]

It's the bitches showing off there boobs in there ads that drive me nuts, like bro this is not Pornhub here.

[@arunks4918]

And third. Done guys.

[@abhaytiwari5991]

Fourth 😁😁😁😁

[@mattmendez8860]

This solution doesn't work anymore BTW, gives TLE

[@darshanputtaswamy3199]

Second

[@akankshasharma7498]

I cannot believe I couldn't solve it on my own 😥😥

[@vikassharma-th7kn]

us moment bhai!!!!

[@lakshyasaharan5348]

First

[@harigovind11]

Thanks for the great explanation! Small suggestion. Better name for dfs function would make the program more readable.

[@Marcox385]

Does it? I mean, depth first search it's a pretty know algorithm with easily identifiable initial, I think it's good the way it is

[@harigovind11]

@@Marcox385 What I meant is making the method name isSafe or something would make it easier to follow the logic once we know it's DFS. But understand some others like the way it is.

[@siqb]

nahh you gotta see his style. It is consistent. That's far more important IMHO. I recognize the dfs immediately.

[@starstarhaha]

in work，good name is necessary ，here not necessary

[@mahesh_kok]

This is Amazing... I have written code following all your videos and code looks like this: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: output = [] for index, ele in enumerate(graph): for inner_ele in ele: output.append((index, inner_ele)) new_graph = {i: [] for i in range(len(graph))} for src, dst in output: new_graph[src].append(dst) if dst not in new_graph: new_graph[dst] = [] stack = [] result = {} def dfs(vertex): if vertex in result: return result[vertex] if vertex in stack: while stack: vertex = stack.pop() result[vertex] = False return False stack.append(vertex) for neighbor in new_graph[vertex]: if not dfs(neighbor): return False if stack: stack.pop() result[vertex] = True return True final_result = [] for node in new_graph: if node not in result: if dfs(node): final_result.append(node) elif result[node]: final_result.append(node) return final_result