Log inSign up
mediumLeetCodeNot Started

Find Eventual Safe States

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[u] is an integer array of nodes adjacent to u, meaning there is a directed edge from u to each node in graph[u].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Constraints:

  • n == graph.length
  • 1 <= n <= 104
  • 0 <= graph[i].length <= n
  • 0 <= graph[i][j] <= n - 1
  • graph[i] is sorted in a strictly increasing order.
  • The graph may contain self-loops.
  • The number of edges in the graph will be in the range [1, 4 * 104].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify safe states as nodes that have no paths to directed cycles.
  • Implement cycle detection using 3-color DFS state tracking.
  • Solve terminal reachability by reversing edge directions (Kahn's Topological Sort).
  • Analyze time and space complexity (O(V + E)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a problem asks for nodes that 'cannot reach any cycle' or 'must eventually terminate', think of cycle detection via DFS 3-coloring or Kahn's algorithm on the reversed graph.

1. DFS Path Simulation from Each Node

Intuition

For every node i, simulate all possible paths using standard DFS. If any path encounters an already visited node on the current path (cycle) or exceeds V steps, node i is not safe. If all branches from i reach terminal nodes, mark i safe.

Algorithm

  1. Initialize safeNodes = [].
  2. For each node i from 0 to n - 1:
  3. Run recursive DFS with a current path set to detect cycles.
  4. If no cycle is found on any branch departing from i, add i to safeNodes.
  5. Return safeNodes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4bool hasCycle(int u, const std::vector<std::vector<int>>& graph, std::vector<bool>& onPath, std::vector<bool>& visited) {
5 onPath[u] = true;
6 for (int v : graph[u]) {
7 if (onPath[v]) return true;
8 if (!visited[v]) {
9 if (hasCycle(v, graph, onPath, visited)) return true;
10 }
11 }
12 onPath[u] = false;
13 visited[u] = true;
14 return false;
15}
16
17std::vector<int> eventualSafeNodesBrute(std::vector<std::vector<int>>& graph) {
18 int n = graph.size();
19 std::vector<int> safeNodes;
20
21 for (int i = 0; i < n; ++i) {
22 std::vector<bool> onPath(n, false);
23 std::vector<bool> visited(n, false);
24 if (!hasCycle(i, graph, onPath, visited)) {
25 safeNodes.push_back(i);
26 }
27 }
28 return safeNodes;
29}
30
31int main() {
32 std::vector<std::vector<int>> graph = {{1,2},{2,3},{5},{0},{5},{},{}};
33 auto res = eventualSafeNodesBrute(graph);
34 std::cout << "Safe Nodes (Brute): ";
35 for (int x : res) std::cout << x << " ";
36 std::cout << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(V * (V + E)) because each node initiates an un-memoized full graph exploration.
  • Space complexity: O(V) for the path recursion stack.

2. DFS with 3-Coloring (White-Gray-Black)

Intuition

Color each node: - 0 (White): unvisited - 1 (Gray): currently being visited (on current recursion stack) - 2 (Black): safe (all paths from here lead to terminal nodes) When exploring node u, set color[u] = 1. If any neighbor is already color 1, a cycle is detected. If all neighbors can be safely colored 2, set color[u] = 2. Because results are memoized across traversals, each vertex and edge is processed once.

Algorithm

  1. Initialize color array of size n filled with 0.
  2. Define dfs(u):
  3. If color[u] > 0, return color[u] == 2.
  4. color[u] = 1 (visiting)
  5. For each neighbor v in graph[u]:
  6. If color[v] == 1 or !dfs(v):
  7. Return false (part of or leads to cycle).
  8. color[u] = 2 (safe)
  9. Return true.
  10. For each i = 0 to n - 1:
  11. If dfs(i), add i to safeNodes.
  12. Return safeNodes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4bool dfsColor(int u, const std::vector<std::vector<int>>& graph, std::vector<int>& color) {
5 if (color[u] > 0) return color[u] == 2;
6
7 color[u] = 1; // gray (visiting)
8 for (int v : graph[u]) {
9 if (color[v] == 1 || !dfsColor(v, graph, color)) {
10 return false;
11 }
12 }
13
14 color[u] = 2; // black (safe)
15 return true;
16}
17
18std::vector<int> eventualSafeNodesDFS(std::vector<std::vector<int>>& graph) {
19 int n = graph.size();
20 std::vector<int> color(n, 0);
21 std::vector<int> safeNodes;
22
23 for (int i = 0; i < n; ++i) {
24 if (dfsColor(i, graph, color)) {
25 safeNodes.push_back(i);
26 }
27 }
28 return safeNodes;
29}
30
31int main() {
32 std::vector<std::vector<int>> graph = {{1,2},{2,3},{5},{0},{5},{},{}};
33 auto res = eventualSafeNodesDFS(graph);
34 std::cout << "Safe Nodes (DFS 3-Color): ";
35 for (int x : res) std::cout << x << " ";
36 std::cout << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(V + E) single DFS traversal visiting each node and edge once.
  • Space complexity: O(V) for the color array and recursion stack.

3. Topological Sort on Reverse Graph (Kahn's Algorithm)

Intuition

Terminal nodes have an out-degree of 0 in the original graph. If we reverse the direction of all edges, terminal nodes become nodes with in-degree 0! Using Kahn's algorithm, repeatedly remove nodes with in-degree 0 and decrement the in-degrees of their outgoing neighbors in the reversed graph. Any node whose in-degree eventually reaches 0 can only lead to terminal nodes and is therefore safe.

Algorithm

  1. Create reversed graph revAdj where each original edge u -> v becomes v -> u.
  2. Track outDegree of original graph (which is the inDegree in the reversed graph).
  3. Initialize queue q. Enqueue all nodes with outDegree[i] == 0 (terminal nodes).
  4. While q is not empty:
  5. u = q.front(), pop queue.
  6. For each neighbor v in revAdj[u]:
  7. outDegree[v]--
  8. If outDegree[v] == 0, push v to q.
  9. Collect all nodes that entered the queue, sort ascending, and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6std::vector<int> eventualSafeNodes(std::vector<std::vector<int>>& graph) {
7 int n = graph.size();
8 std::vector<std::vector<int>> revAdj(n);
9 std::vector<int> outDegree(n, 0);
10
11 for (int u = 0; u < n; ++u) {
12 outDegree[u] = graph[u].size();
13 for (int v : graph[u]) {
14 revAdj[v].push_back(u);
15 }
16 }
17
18 std::queue<int> q;
19 for (int i = 0; i < n; ++i) {
20 if (outDegree[i] == 0) {
21 q.push(i);
22 }
23 }
24
25 std::vector<bool> isSafe(n, false);
26 while (!q.empty()) {
27 int u = q.front();
28 q.pop();
29 isSafe[u] = true;
30
31 for (int v : revAdj[u]) {
32 if (--outDegree[v] == 0) {
33 q.push(v);
34 }
35 }
36 }
37
38 std::vector<int> safeNodes;
39 for (int i = 0; i < n; ++i) {
40 if (isSafe[i]) {
41 safeNodes.push_back(i);
42 }
43 }
44 return safeNodes;
45}
46
47int main() {
48 std::vector<std::vector<int>> graph = {{1,2},{2,3},{5},{0},{5},{},{}};
49 auto res = eventualSafeNodes(graph);
50 std::cout << "Optimal Safe Nodes (Kahn Reverse): ";
51 for (int x : res) std::cout << x << " ";
52 std::cout << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(V + E) to reverse graph and execute Kahn's algorithm, plus O(V log V) to sort safe node IDs.
  • Space complexity: O(V + E) for the reversed adjacency list and in-degree array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS Path SimulationO(V * (V + E))O(V)Simple intuitive check from each node.Repeatedly traverses the same graph sections without global memoization.
2.DFS with 3-ColoringO(V + E)O(V)Direct in-place cycle memoization; very concise implementation.Uses recursion stack of depth V.
3.Kahn's on Reversed GraphOptimalO(V + E)O(V + E)Iterative queue-based; no recursion call-stack limits; natural topological peel from terminal nodes.Requires constructing the reversed adjacency list.

Common Pitfalls & Crucial Edge Cases

Assuming nodes that reach a safe node are safe without verifying ALL branches.

A node is safe if and only if EVERY branch from it leads to a terminal node. If even one branch enters a cycle, the node is unsafe.

Forgetting to sort the resulting safe node list.

The problem asks for safe nodes in ascending sorted order. Checking from 0 to n - 1 naturally produces sorted results.

Crucial Edge Cases to Validate:

  • Graph is entirely disconnected with 0 edges — All nodes are terminal nodes (out-degree 0); returns all nodes [0, 1, ..., n-1].
  • Self-loops (e.g., node 0 has edge to 0) — Detected as a cycle; node 0 is correctly identified as unsafe.
  • DAG with no cycles — All nodes eventually lead to terminal nodes; returns all nodes.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the core insight: 'Safe nodes are nodes that cannot reach any directed cycle.'
  2. Describe both solutions: DFS 3-coloring (cycle detection memoization) and Reverse Graph Topological Sort (peeling from terminal nodes).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the defining characteristic of an unsafe node?

2.In the 3-coloring DFS approach, what does color 1 indicate?

3.Is every terminal node automatically a safe node?

Back to DSA Sheet