Find Eventual Safe States - Leetcode 802 - Python

0:00 - Read the problem
0:55 - Drawing Explanation
5:10 - Walk Through Example
9:50 - Coding Explanation

leetcode 802

#microsoft #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[amegahed]

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.

[donghyunsuh]

This was my solution after I saw Neetcode's drawing explanation:

def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
status = {}

def dfs(node):
if node in status:
return status[node]

status[node] = False

res = True
for neighbor in graph[node]:
res = dfs(neighbor) and res

status[node] = res
return res

res = []
for i in range(len(graph)):
if dfs(i):
res.append(i)

return res

[juhairahamed]

Good Explanation. Get new way of thinking

[AlancRodriguez]

A genius can make a complex topic seem simple

[Man_of_Culture.]

Solution optimized with dp (safe vector used as dp) concept
class Solution {
public:
bool dfs(int u, vector<bool>&visited, vector<bool>&safe, vector<vector<int>>& 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<int> graph) {
int n=graph.size();
vector<bool>visited(n, 0), safe(n, 0);
for(int i=0;i<n;i+=1)
{
if(graph[i].size()==0)
safe[i]=1;
}
for(int i=0;i<n;i+=1)
{
if(!visited[i])
dfs(i, visited, safe, graph);
}
vector<int>res;
for(int i=0;i<n;i+=1)
if(safe[i])
res.push_back(i);
return res;
}
};

[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

[tommasodonato]

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

[mehulsolanki]

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

[sidazhong]

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.

[schan]

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

[mattmendez]

This solution doesn't work anymore BTW, gives TLE

[akankshasharma]

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

[harigovind]

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