Find Eventual Safe States

LeetCode 802: Find Eventual Safe States Solution & Explanation

Problem Overview

TL;DR: We perform a Depth-First Search (DFS) with 3-color state tracking (unvisited, visiting, safe) to detect cycles; any node that is part of or leads to a cycle is unsafe, while all others are safe.

The Find Eventual Safe States problem asks us to identify all nodes in a directed graph that are "safe." A node is considered safe if every possible path starting from it eventually leads to a terminal node (a node with no outgoing edges). In simpler terms, a node is safe if it is impossible to get stuck in a loop (cycle) starting from that node. If you start at a safe node and keep moving, you will guaranteed stop eventually.

This is a classic graph problem often appearing in technical interviews, including those at Amazon. It essentially boils down to identifying nodes that are not part of any cycle and do not lead to any cycle.

Brute Force Approach for Find Eventual Safe States

The naive approach is to simulate all possible paths from every single node to see if they terminate. For each node i from 0 to n-1, we perform a traversal (like DFS). If the traversal encounters a node that is currently in the recursion stack, we have found a cycle, meaning the starting node is not safe.

1# Pseudo-code for Brute Force
2def is_safe(node, visited):
3    if node in visited: return False # Cycle detected
4    visited.add(node)
5    for neighbor in graph[node]:
6        if not is_safe(neighbor, visited):
7            return False
8    visited.remove(node)
9    return True
10
11result = []
12for i in range(n):
13    if is_safe(i, set()):
14        result.append(i)
15return result

Time Complexity: $O(V \cdot (V + E))$. In the worst case, for every node, we might traverse a large portion of the graph. Why it fails: This approach results in a Time Limit Exceeded (TLE) error. The constraints allow up to $10^4$ nodes. Re-traversing the same paths repeatedly for different starting nodes performs highly redundant work. We need a way to remember (memoize) whether a node is safe or unsafe once we process it.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

1. State Initialization: Create an array color of size n initialized to 0 (Unvisited).
2. Global Iteration: Iterate through every node i from 0 to n-1. If color[i] is 0, start a DFS from i.
3. DFS Logic (Cycle Detection):
   • Check State: If the current node u is 1 (Visiting), a cycle is detected; return false (unsafe). If u is 2 (Safe), return true.
   • Mark Visiting: Set color[u] = 1.
   • Process Neighbors: Iterate through all neighbors v of u.
     • If color[v] == 2, skip (it's already safe).
     • If color[v] == 1 OR dfs(v) returns false, then u leads to a cycle. We leave color[u] as 1 (which we treat as unsafe) and return false.
   • Mark Safe: If all neighbors are processed successfully without finding a cycle, mark color[u] = 2 and return true.
4. Result Collection: After checking all nodes, collect all indices i where color[i] == 2 into a sorted list.

Execution Flow

Let's trace the algorithm with a simple example: 0 -> 1 -> 0 (Cycle) and 2 -> 1.

1. Start Loop: i = 0. color[0] is 0. Call dfs(0).
2. DFS(0): Mark color[0] = 1. Neighbor is 1.
3. DFS(1): Mark color[1] = 1. Neighbor is 0.
4. Check Neighbor 0: color[0] is 1. Cycle detected! Return false.
5. Back to DFS(1): Received false from neighbor 0. Return false. color[1] remains 1.
6. Back to DFS(0): Received false from neighbor 1. Return false. color[0] remains 1.
7. Loop continues: i = 1. color[1] is 1. It was visited and determined unsafe. Skip or treat as processed.
8. Loop continues: i = 2. color[2] is 0. Call dfs(2).
9. DFS(2): Mark color[2] = 1. Neighbor is 1.
10. Check Neighbor 1: color[1] is 1. This means it is unsafe (either in stack or previously failed). Return false.
11. Back to DFS(2): Received false from neighbor 1. Return false. color[2] remains 1.
12. Final Result: No nodes marked 2. Result [].

Note: In this logic, state 1 serves double duty as "Visiting" and "Unsafe". State 2 is strictly "Safe".

Proof of Correctness

The correctness relies on the invariant of the 3-color DFS.

1. Cycle Detection: A directed graph has a cycle if and only if a DFS encounters a back-edge to a node currently in the recursion stack (state 1). Our algorithm explicitly checks for this.
2. Propagation: If a node u has a neighbor v that is part of a cycle (or leads to one), dfs(v) will return false. Consequently, dfs(u) will also return false, correctly identifying u as unsafe.
3. Terminal Nodes: A terminal node has no neighbors. The loop over neighbors completes immediately, the node is marked 2 (Safe), and true is returned. This forms the base case for safety.
4. Completeness: By iterating 0 to n-1, we ensure every component of the graph is processed. Memoization ensures each node is computed exactly once.

Pattern Reuse Notes

The Graph DFS - Cycle Detection pattern is a fundamental tool for solving directed graph problems involving dependencies or infinite loops.

• LeetCode 207: Course Schedule: This is the exact same pattern. A course schedule is valid if and only if the graph has no cycles.
• LeetCode 210: Course Schedule II: Similar to Course Schedule I, but requires returning the topological sort order if no cycle exists.
• LeetCode 1059: All Paths from Source Lead to Destination: Requires ensuring all paths from a source end at a specific destination, which implicitly requires cycle detection.

Reference Implementation

C++ Solution for LeetCode 802

1class Solution {
2public:
3    // 0: Unvisited
4    // 1: Visiting (in stack) or Unsafe
5    // 2: Safe
6    bool dfs(int node, vector<vector<int>>& graph, vector<int>& color) {
7        if (color[node] != 0) {
8            return color[node] == 2;
9        }
10
11        color[node] = 1; // Mark as visiting
12
13        for (int neighbor : graph[node]) {
14            if (color[neighbor] == 2) continue; // Safe node, skip
15            if (color[neighbor] == 1 || !dfs(neighbor, graph, color)) {
16                return false; // Cycle detected or leads to unsafe node
17            }
18        }
19
20        color[node] = 2; // Mark as safe
21        return true;
22    }
23
24    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
25        int n = graph.size();
26        vector<int> color(n, 0);
27        vector<int> safeNodes;
28
29        for (int i = 0; i < n; ++i) {
30            if (dfs(i, graph, color)) {
31                safeNodes.push_back(i);
32            }
33        }
34
35        return safeNodes;
36    }
37};

Java Solution for LeetCode 802

1class Solution {
2    // 0: Unvisited, 1: Visiting/Unsafe, 2: Safe
3    public List<Integer> eventualSafeNodes(int[][] graph) {
4        int n = graph.length;
5        int[] color = new int[n];
6        List<Integer> result = new ArrayList<>();
7
8        for (int i = 0; i < n; i++) {
9            if (dfs(i, graph, color)) {
10                result.add(i);
11            }
12        }
13        return result;
14    }
15
16    private boolean dfs(int node, int[][] graph, int[] color) {
17        if (color[node] != 0) {
18            return color[node] == 2;
19        }
20
21        color[node] = 1; // Mark as visiting
22
23        for (int neighbor : graph[node]) {
24            if (color[neighbor] == 2) continue;
25            if (color[neighbor] == 1 || !dfs(neighbor, graph, color)) {
26                return false;
27            }
28        }
29
30        color[node] = 2; // Mark as safe
31        return true;
32    }
33}

Python Solution for LeetCode 802

1class Solution:
2    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
3        n = len(graph)
4        # 0: Unvisited
5        # 1: Visiting (in recursion stack) or Unsafe
6        # 2: Safe
7        color = [0] * n
8
9        def dfs(node):
10            if color[node] != 0:
11                return color[node] == 2
12            
13            color[node] = 1 # Mark as visiting
14            
15            for neighbor in graph[node]:
16                if color[neighbor] == 2:
17                    continue
18                if color[neighbor] == 1 or not dfs(neighbor):
19                    return False
20            
21            color[node] = 2 # Mark as safe
22            return True
23
24        res = []
25        for i in range(n):
26            if dfs(i):
27                res.append(i)
28        
29        return res