Find Eventual Safe States - Leetcode Solution

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).

1