We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Eventual Safe States

Number: 820

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Bloomberg, Amazon, Adobe, Meta, Uber

Problem Description

Given a directed graph where each node is labeled from 0 to n - 1 and represented as an array of neighbors, a terminal node is one with no outgoing edges and a safe node is one where every path starting from it eventually leads to a terminal (or another safe) node. The task is to return all safe nodes in ascending order.

Key Insights

  • Identify cycles: Nodes involved in cycles are unsafe because there exists a path that does not terminate.
  • DFS with state tracking: Use three states for each node (unvisited, visiting, and safe) to detect cycles.
  • Memorization: Once a node's safety is determined, reuse this result to avoid redundant computations.
  • Alternate approach: Reverse the graph and perform a topological sort, though DFS is more straightforward here.

Space and Time Complexity

Time Complexity: O(V + E) where V is the number of nodes and E is the number of edges.
Space Complexity: O(V) due to the recursion stack and additional storage for tracking node states.

Solution

We perform a depth-first search (DFS) and use an array to mark each node with one of three states:

  • 0: unvisited
  • 1: visiting (currently in recursion stack)
  • 2: safe (confirmed safe node)

For each node, if during DFS a node is encountered that is already marked as visiting, a cycle is detected and the node is unsafe. If all reachable neighbors of a node are safe, then the node itself is safe. Finally, we collect and return all safe nodes sorted in ascending order.

Code Solutions

# Python solution using DFS and state tracking.
# States: 0 = unvisited, 1 = visiting, 2 = safe.
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        state = [0] * n  # Initialize all nodes as unvisited.

        def dfs(node):
            # If node is already processed, return True if safe.
            if state[node] != 0:
                return state[node] == 2
            state[node] = 1  # Mark node as visiting.
            for neighbor in graph[node]:
                # If any neighbor leads to a cycle, node is unsafe.
                if not dfs(neighbor):
                    return False
            state[node] = 2  # All neighbors are safe, mark node as safe.
            return True

        safe_nodes = []
        for i in range(n):
            if dfs(i):
                safe_nodes.append(i)
        return safe_nodes
← Back to All Questions