802. Find Eventual Safe States

At a Glance

Topic: advanced-graphs
Pattern: Topological sort on reverse graph or DFS three-color cycle detection
Difficulty: Hard
Companies: Google, Amazon, Apple, DoorDash, Bolt
Frequency: High
LeetCode: 802

Directed graph on 0..n-1. A node is eventually safe if every path from it eventually reaches a terminal (out-degree 0) node and never enters a cycle. Return all such nodes in ascending order.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Safe ⇔ not on a cycle and cannot reach a cycle
Reverse edges from terminals — nodes that can only reach safe sinks peel like topo sort
Same structure as “nodes not in cycle graph” for functional graphs variant

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DFS memo colors — gray stack = cycle — O(V+E).
Reverse graph + Kahn — start from outdegree-zero — O(V+E) — often easiest to explain.

Optimal Solution

Go

func eventualSafeNodes(graph [][]int) []int {
	nodeCount := len(graph)
	reverse := make([][]int, nodeCount)
	outdegree := make([]int, nodeCount)
	for from := 0; from < nodeCount; from++ {
		outdegree[from] = len(graph[from])
		for _, to := range graph[from] {
			reverse[to] = append(reverse[to], from)
		}
	}
	queue := make([]int, 0)
	for node := 0; node < nodeCount; node++ {
		if outdegree[node] == 0 {
			queue = append(queue, node)
		}
	}
	safe := make([]bool, nodeCount)
	head := 0
	for head < len(queue) {
		current := queue[head]
		head++
		safe[current] = true
		for _, incoming := range reverse[current] {
			outdegree[incoming]--
			if outdegree[incoming] == 0 {
				queue = append(queue, incoming)
			}
		}
	}
	result := []int{}
	for node := 0; node < nodeCount; node++ {
		if safe[node] {
			result = append(result, node)
		}
	}
	return result
}

JavaScript

function eventualSafeNodes(graph) {
  const nodeCount = graph.length;
  const reverse = Array.from({ length: nodeCount }, () => []);
  const outdegree = new Array(nodeCount).fill(0);
  for (let from = 0; from < nodeCount; from += 1) {
    outdegree[from] = graph[from].length;
    for (const to of graph[from]) {
      reverse[to].push(from);
    }
  }
  const queue = [];
  for (let node = 0; node < nodeCount; node += 1) {
    if (outdegree[node] === 0) {
      queue.push(node);
    }
  }
  const safe = new Array(nodeCount).fill(false);
  while (queue.length > 0) {
    const current = queue.shift();
    safe[current] = true;
    for (const incoming of reverse[current]) {
      outdegree[incoming] -= 1;
      if (outdegree[incoming] === 0) {
        queue.push(incoming);
      }
    }
  }
  const result = [];
  for (let node = 0; node < nodeCount; node += 1) {
    if (safe[node]) {
      result.push(node);
    }
  }
  return result;
}

Walkthrough

Terminal nodes have outdegree 0; peel them, decrement predecessors’ effective remaining “dangerous” exits; when all outgoing edges lead only into eliminated-safe structure, node becomes safe.

Invariant: Node becomes safe exactly when all outgoing neighbors are already known safe (topological peel on reverse reachability).

Edge Cases

Empty neighbor lists everywhere — all nodes safe
Single self-loop — node unsafe
DAG — all nodes safe

Pitfalls

Confusing reachable cycle vs on cycle — must exclude nodes that can reach a cycle even if not on it
Sorting output — ascending required

Variants

Coloring / memo DFS — mark 0/1/2 for unvisited, visiting, safe; same O(V+E).
Functional graph (out-degree 1) — fast cycle finding with two pointers.
Count safe nodes only — same algorithm, output length.

Mind-Map Tags

#reverse-topo #outdegree-peel #safe-states #directed-acyclic-condensation