Find Eventual Safe States

1. Define the problem

You are given a directed graph of n nodes, where graph_i is the list of nodes that node i points to. A node is safe if every path starting from it eventually reaches a terminal node — one with no outgoing edges — instead of looping forever. Return all safe nodes, sorted in ascending order . Work from the terminal nodes backward , peeling off a node as safe once every node it points to has already been confirmed safe — a topological sort over the reversed graph.

Constraints

n == graph.length
1 ≤ n ≤ 10⁴
0 ≤ graph_i.length ≤ n
0 ≤ graph_i[j] < n

Example

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

Output[2, 4, 5, 6]

Explanation 5 and 6 are terminal. 2 only leads to 5, and 4 only leads to 5 — both are safe too.

2. Know the words first

In plain terms

Safe node: A node that can never be part of a cycle and never leads into one — no matter which path you take from it, you always end up stuck at a dead end.
Terminal node: A node with no outgoing edges at all — a dead end, and therefore always safe.

3. Visualize the solution

Peel safe nodes inward, starting from every terminal node

Statusinit

out-degree: 0=2, 1=2, 2=1, 3=1, 4=1, 5=0, 6=0. Terminal nodes 5 and 6 are safe immediately.

What happens in this step

out-degree[0] = 2, out-degree[1] = 2, out-degree[2] = 1, out-degree[3] = 1, out-degree[4] = 1
out-degree[5] = 0, out-degree[6] = 0

queue = [5, 6]

Nodes 5 and 6 point nowhere — they're terminal, so they're safe by definition and start the queue.

Step 1 of 4

Steps to visualize

Count each node's out-degree and build a reversed graph (who points to this node).
Queue every terminal node — out-degree zero — and mark it safe.
Pop a safe node; for every node that points to it, decrement that node's out-degree.
Any node whose out-degree just hit zero is now safe too, and joins the queue.
The final safe set is every node the peeling reached.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Peel safe nodes inward, starting from every terminal node

Statusinit

out-degree: 0=2, 1=2, 2=1, 3=1, 4=1, 5=0, 6=0. Terminal nodes 5 and 6 are safe immediately.

What happens in this step

out-degree[0] = 2, out-degree[1] = 2, out-degree[2] = 1, out-degree[3] = 1, out-degree[4] = 1
out-degree[5] = 0, out-degree[6] = 0

queue = [5, 6]

Nodes 5 and 6 point nowhere — they're terminal, so they're safe by definition and start the queue.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function eventualSafeNodes(n, graph) {
  const outDegree = graph.map((neighbors) => neighbors.length);
  const reverseGraph = Array.from({ length: n }, () => []);

  for (let i = 0; i < n; i++) {
    for (const j of graph[i]) {
      reverseGraph[j].push(i);
    }
  }

  const safe = new Array(n).fill(false);
  const queue = [];
  for (let i = 0; i < n; i++) {
    if (outDegree[i] === 0) {
      queue.push(i);
    }
  }

  while (queue.length > 0) {
    const node = queue.shift();
    safe[node] = true;
    for (const prev of reverseGraph[node]) {
      outDegree[prev]--;
      if (outDegree[prev] === 0) {
        queue.push(prev);
      }
    }
  }

  const result = [];
  for (let i = 0; i < n; i++) {
    if (safe[i]) {
      result.push(i);
    }
  }
  return result;
}

Time: O(n + edges)
Space: O(n + edges)

6. Test cases

Test cases

Input	Expected	Covers
`n = 7, graph = [[1,2],[2,3],[5],[0],[5],[],[]]`	`[2, 4, 5, 6]`	example from the docstring, mixing safe nodes with a 0-1-3 cycle
`n = 3, graph = [[],[],[]]`	`[0, 1, 2]`	every node is already terminal, so every node is safe
`n = 2, graph = [[1],[0]]`	`[]`	a simple two-node cycle with no safe nodes at all
`n = 4, graph = [[1],[2],[3],[]]`	`[0, 1, 2, 3]`	a straight chain leading to a dead end — every node is safe
`n = 5, graph = [[1],[2],[3],[4],[2]]`	`[]`	no node has out-degree zero, so nothing can ever be marked safe
`n = 1, graph = [[]]`	`[0]`	smallest valid input, a single terminal node
`n = 6, graph = [[1,2],[3],[3],[],[5],[4]]`	`[0, 1, 2, 3]`	a safe branch (0,1,2,3) alongside an unrelated 4-5 cycle
`n = 3, graph = [[0],[],[]]`	`[1, 2]`	a node pointing to itself can never be marked safe, even though its neighbors are terminal

Find Eventual Safe States