Skip to main content

25. Find Eventual Safe States

mediumAsked at CircleCI

Find all nodes that eventually lead to terminal nodes (no cycles), analogous to identifying pipeline jobs guaranteed to terminate versus those caught in retry loops.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a directed graph as an adjacency list, a node is safe if every path from it leads to a terminal node (out-degree 0) or another safe node. Return all safe nodes in sorted order.

Constraints

  • n == graph.length
  • 1 <= n <= 10^4
  • 0 <= graph[i].length <= n
  • graph[i] is sorted and unique

Examples

Example 1

Input
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output
[2,4,5,6]

Example 2

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

Approaches

1. DFS three-color cycle detection

Mark nodes as unsafe if they're part of a cycle; safe otherwise using post-order DFS.

Time
O(V+E)
Space
O(V)
function eventualSafeNodes(graph) {
  const n = graph.length;
  const state = new Array(n).fill(0); // 0=unvisited,1=visiting,2=safe,3=unsafe
  function dfs(node) {
    if (state[node] === 1) { state[node] = 3; return false; }
    if (state[node] === 2) return true;
    if (state[node] === 3) return false;
    state[node] = 1;
    for (const nb of graph[node]) {
      if (!dfs(nb)) { state[node] = 3; return false; }
    }
    state[node] = 2; return true;
  }
  for (let i = 0; i < n; i++) dfs(i);
  return Array.from({length: n}, (_,i) => i).filter(i => state[i] === 2);
}

Tradeoff:

2. Reverse graph + Kahn's BFS

Reverse all edges, then apply Kahn's topological sort from original terminal nodes; nodes reachable from terminals in the reversed graph are safe.

Time
O(V+E)
Space
O(V+E)
function eventualSafeNodes(graph) {
  const n = graph.length;
  const rev = Array.from({length: n}, () => []);
  const outdegree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    outdegree[u] = graph[u].length;
    for (const v of graph[u]) rev[v].push(u);
  }
  const queue = [];
  for (let i = 0; i < n; i++) if (outdegree[i] === 0) queue.push(i);
  const safe = new Array(n).fill(false);
  while (queue.length) {
    const u = queue.shift(); safe[u] = true;
    for (const v of rev[u]) { if (--outdegree[v] === 0) queue.push(v); }
  }
  return Array.from({length: n}, (_,i) => i).filter(i => safe[i]);
}

Tradeoff:

CircleCI-specific tips

CircleCI uses this concept to identify pipeline jobs stuck in circular retry dependencies — explain the reverse-graph Kahn's approach as it aligns with how they propagate 'terminates-safely' signals upstream through the DAG.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find Eventual Safe States and other CircleCI interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →