LeetCode 802 - Find Eventual Safe States

LeetCode Problem 802

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a directed graph represented as an adjacency list. Each node represents a state, and each directed edge represents a possible transition from one node to another.

The input graph[i] contains all nodes that can be reached directly from node i. If graph[i] is empty, then node i is a terminal node because there are no outgoing edges.

The goal is to determine which nodes are "eventually safe." A node is considered safe if every possible path starting from that node eventually ends at a terminal node. In other words, no matter which outgoing edges we follow, we can never get trapped in a cycle.

This definition is important because a node becomes unsafe if even one possible path leads into a cycle. A cycle means we could continue traversing forever without reaching a terminal node.

Consider the following situations:

• A terminal node is always safe because it already ends immediately.
• A node that only points to safe nodes is also safe.
• A node that can reach a cycle is unsafe.
• Any node inside a cycle is unsafe.

The constraints tell us that:

• There can be up to 10^4 nodes.
• There can be up to 4 * 10^4 edges.

This means we need an algorithm close to linear time, specifically O(V + E), where:

• V is the number of vertices
• E is the number of edges

A naive approach that repeatedly explores paths from every node independently may become too slow.

There are several edge cases worth noticing immediately:

• Self-loops such as 0 -> 0 create cycles, so those nodes are unsafe.
• Disconnected components may exist, so we must evaluate every node independently.
• A node may have multiple outgoing edges, where only one leads to a cycle. That node is still unsafe.
• Large graphs require avoiding repeated DFS traversals whenever possible.

The key challenge is identifying which nodes are guaranteed not to participate in or reach any cycle.

Approaches

Brute Force Approach

A straightforward approach is to start a DFS from every node independently and determine whether that traversal eventually reaches a cycle.

For each node:

1. Perform DFS.
2. Track the current recursion path.
3. If we revisit a node already in the current DFS path, we found a cycle.
4. If all paths terminate safely, mark the node as safe.

This works because DFS naturally explores all possible reachable paths from a node.

However, this approach becomes inefficient because many subgraphs are explored repeatedly. If multiple nodes share the same descendants, we recompute the same results over and over again.

In the worst case, DFS from every node may traverse nearly the entire graph.

Optimal Approach, DFS With State Coloring

The key insight is that graph safety depends entirely on cycle detection.

A node is safe if and only if it cannot reach a cycle.

Instead of recomputing results repeatedly, we can classify nodes into states during DFS:

• 0 = unvisited
• 1 = visiting, currently in recursion stack
• 2 = safe, already verified

During DFS:

• If we encounter a node marked 1, we found a cycle.
• If we encounter a node marked 2, we already know it is safe.
• A node becomes safe only after all its neighbors are confirmed safe.

This avoids repeated computation because each node is processed once.

The algorithm effectively memoizes DFS results.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(V × (V + E))	O(V)	Repeats DFS work for many nodes
Optimal	O(V + E)	O(V)	DFS with memoized node states

Algorithm Walkthrough

Optimal DFS State Coloring Algorithm

1. Create a state array of size n.

Each node can be in one of three states:

• 0 = unvisited
• 1 = visiting
• 2 = safe

This array allows us to detect cycles and avoid repeated work. 2. Define a DFS function for a node.

The DFS function returns True if the node is safe and False otherwise. 3. If the node is currently marked as 1, return False.

This means we encountered the node again while still exploring it, which indicates a cycle. 4. If the node is already marked as 2, return True.

We already proved this node is safe earlier. 5. Mark the current node as 1.

This indicates the node is currently inside the recursion stack. 6. Explore all outgoing neighbors.

For every neighbor:

• Run DFS recursively.
• If any neighbor is unsafe, immediately return False.

A node is only safe if every possible outgoing path is safe. 7. After all neighbors are verified safe, mark the current node as 2.

This permanently records the node as safe. 8. Run DFS for every node from 0 to n - 1.

If DFS returns True, append the node to the result list. 9. Return the result list.

Since we process nodes in increasing order, the output is automatically sorted.

Why it works

The algorithm maintains a critical invariant:

• A node is marked safe only after every reachable path from that node is verified safe.

Cycle detection works because any revisit to a node currently in the recursion stack indicates a directed cycle.

Memoization works because once a node is proven safe, its result never changes. Every future DFS can reuse that information immediately.

Since every node and edge is processed at most once, the algorithm is both correct and efficient.

Python Solution

from typing import List

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)

        # 0 = unvisited
        # 1 = visiting
        # 2 = safe
        state = [0] * n

        def dfs(node: int) -> bool:
            # Found a cycle
            if state[node] == 1:
                return False

            # Already known to be safe
            if state[node] == 2:
                return True

            # Mark as visiting
            state[node] = 1

            # Explore neighbors
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            # All neighbors are safe
            state[node] = 2
            return True

        result = []

        for node in range(n):
            if dfs(node):
                result.append(node)

        return result

The implementation begins by creating the state array, which tracks the DFS status of every node.

The nested dfs function performs the actual cycle detection and safety verification.

The first condition checks whether the node is currently being visited. If so, we discovered a cycle because the node appears again in the active recursion path.

The second condition checks whether the node has already been confirmed safe. This acts as memoization and prevents repeated traversal.

When visiting a new node, we mark it as 1 before exploring neighbors. This is essential for cycle detection.

The loop iterates through every outgoing neighbor. If any neighbor is unsafe, the current node must also be unsafe because at least one path leads to a cycle.

If all neighbors are safe, we mark the node as 2, meaning it is permanently verified safe.

Finally, we run DFS from every node and collect all nodes whose DFS returns True.

Go Solution

func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)

	// 0 = unvisited
	// 1 = visiting
	// 2 = safe
	state := make([]int, n)

	var dfs func(int) bool

	dfs = func(node int) bool {
		// Found a cycle
		if state[node] == 1 {
			return false
		}

		// Already known safe
		if state[node] == 2 {
			return true
		}

		// Mark as visiting
		state[node] = 1

		// Explore neighbors
		for _, neighbor := range graph[node] {
			if !dfs(neighbor) {
				return false
			}
		}

		// Mark as safe
		state[node] = 2
		return true
	}

	result := []int{}

	for node := 0; node < n; node++ {
		if dfs(node) {
			result = append(result, node)
		}
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used for both the adjacency list and the state array. Go does not distinguish between lists and arrays in the same way Python does, so slices are the natural choice.

The recursive DFS function is declared using a function variable so it can recursively reference itself.

There are no integer overflow concerns because node indices are bounded by the problem constraints.

An empty adjacency list naturally represents terminal nodes, exactly as in Python.

Worked Examples

Example 1

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Initial State

Node	State
0	0
1	0
2	0
3	0
4	0
5	0
6	0

DFS From Node 0

0 -> 1 -> 3 -> 0

Cycle detected.

Nodes 0, 1, and 3 are unsafe.

DFS From Node 2

2 -> 5

Node 5 is terminal.

So:

Node	Final State
2	2
5	2

DFS From Node 4

4 -> 5

Since 5 is already safe, 4 is also safe.

DFS From Node 6

6 has no outgoing edges.

So 6 is safe immediately.

Final Safe Nodes

[2,4,5,6]

Example 2

graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

DFS Traversal

Starting from node 0:

0 -> 1 -> 1

Self-cycle detected at node 1.

This makes node 1 unsafe.

Since 0 can reach 1, node 0 is also unsafe.

Node 2 reaches node 3, which reaches node 0, so 2 is unsafe.

Node 3 participates in the cycle involving 0.

Only node 4 is terminal.

Final Safe Nodes

[4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V + E)	Each node and edge is processed at most once
Space	O(V)	State array and recursion stack

The DFS traversal touches every node at most once after memoization takes effect.

Every directed edge is explored once during DFS.

The recursion stack can grow up to O(V) in the worst case for a deep graph.

Test Cases

sol = Solution()

# Provided example 1
assert sol.eventualSafeNodes(
    [[1,2],[2,3],[5],[0],[5],[],[]]
) == [2,4,5,6]

# Provided example 2
assert sol.eventualSafeNodes(
    [[1,2,3,4],[1,2],[3,4],[0,4],[]]
) == [4]

# Single terminal node
assert sol.eventualSafeNodes(
    [[]]
) == [0]

# Single self-loop
assert sol.eventualSafeNodes(
    [[0]]
) == []

# Simple cycle
assert sol.eventualSafeNodes(
    [[1],[2],[0]]
) == []

# Linear acyclic graph
assert sol.eventualSafeNodes(
    [[1],[2],[3],[]]
) == [0,1,2,3]

# Mixed safe and unsafe nodes
assert sol.eventualSafeNodes(
    [[1],[2],[1],[]]
) == [3]

# Multiple disconnected components
assert sol.eventualSafeNodes(
    [[1],[],[3],[2]]
) == [0,1]

# Node with one safe path and one cyclic path
assert sol.eventualSafeNodes(
    [[1,2],[3],[2],[]]
) == [1,3]

# Larger DAG
assert sol.eventualSafeNodes(
    [[1,2],[3],[3],[],[0]]
) == [0,1,2,3,4]

Test	Why
Example 1	Validates mixed cyclic and safe regions
Example 2	Validates cycle propagation
Single terminal node	Smallest safe graph
Single self-loop	Detects direct cycles
Simple cycle	Ensures all cyclic nodes are unsafe
Linear acyclic graph	Ensures all DAG nodes are safe
Mixed safe and unsafe nodes	Validates selective safety
Multiple disconnected components	Ensures full graph traversal
One safe and one cyclic path	Verifies "all paths" requirement
Larger DAG	Confirms correctness on acyclic graphs

Edge Cases

Self-Loops

A node may point to itself, such as 0 -> 0.

This is a cycle of length one. A naive implementation that only checks for repeated neighbors without tracking recursion state may fail to detect it correctly.

The DFS coloring approach handles this naturally because the node becomes marked as visiting before exploring neighbors. When DFS reaches the same node again, the algorithm immediately detects a cycle.

Nodes With Mixed Outgoing Paths

A node may have multiple outgoing edges where some paths are safe and others reach cycles.

For example:

0 -> 1
0 -> 2
2 -> 2

Even though one path from 0 is safe, the existence of a cyclic path makes node 0 unsafe.

The implementation correctly handles this because every neighbor must return True before the current node can be marked safe.

Disconnected Graph Components

The graph may contain several disconnected sections.

Some components may be entirely safe while others contain cycles.

A solution that only starts DFS from a single node would miss parts of the graph.

The implementation explicitly runs DFS for every node from 0 to n - 1, ensuring all components are evaluated independently.