## Similar Problems

Similar Problems not available

# Find Eventual Safe States - Leetcode Solution

## Companies:

LeetCode: Find Eventual Safe States Leetcode Solution

Difficulty: Medium

Topics: graph depth-first-search breadth-first-search

Problem Description:

In this problem, we are given an array of nodes, each of which represents a state. We have to find all the states that are "eventually safe". A state is said to be eventually safe if we can start at this state and perform any number of transitions to arrive at a terminal state, which is a state that has no outgoing edges.

Solution:

To solve this problem, we can make use of a recursive function that checks whether a given state is eventually safe or not. We start with the state s and follow all the outgoing edges from s. If any of these edges lead to a state that is not eventually safe, then s is also not eventually safe. Otherwise, we can mark s as eventually safe and return True. We can memoize the answer for all the states that we have already visited, so that we don't have to repeat the computation.

Code in Python:

We can implement our solution using the following recursive function:

```
def is_eventually_safe(state: int, graph: List[List[int]], visited: List[int]) -> bool:
if visited[state] == 1:
return False
if visited[state] == 2:
return True
visited[state] = 1
for nxt in graph[state]:
if not is_eventually_safe(nxt, graph, visited):
return False
visited[state] = 2
return True
```

We can call this function for each state in the graph, and mark the states that return True as eventually safe. We can implement the main function as follows:

```
from typing import List
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
results = []
visited = [0] * n
for i in range(n):
if is_eventually_safe(i, graph, visited):
results.append(i)
return results
```

This solution has a time complexity of O(n + e), where e is the number of edges in the graph, and a space complexity of O(n).

## Find Eventual Safe States Solution Code

`1`