LeetCode #802 — MEDIUM

Find Eventual Safe States

Move from brute-force thinking to an efficient approach using topological sort strategy.

The Problem

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[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

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.

Example 1:

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2:

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints:

n == graph.length
1 <= n <= 10⁴
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 * 10⁴].

Step 01

Brute Force Baseline

Problem summary: 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[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i]. 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Topological Sort

Example 1

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

Example 2

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

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #802: Find Eventual Safe States
class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] indeg = new int[n];
        List<Integer>[] rg = new List[n];
        Arrays.setAll(rg, k -> new ArrayList<>());
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            for (int j : graph[i]) {
                rg[j].add(i);
            }
            indeg[i] = graph[i].length;
            if (indeg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int i = q.pollFirst();
            for (int j : rg[i]) {
                if (--indeg[j] == 0) {
                    q.offer(j);
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (indeg[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #802: Find Eventual Safe States
func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)
	indeg := make([]int, n)
	rg := make([][]int, n)
	q := []int{}
	for i, vs := range graph {
		for _, j := range vs {
			rg[j] = append(rg[j], i)
		}
		indeg[i] = len(vs)
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		for _, j := range rg[i] {
			indeg[j]--
			if indeg[j] == 0 {
				q = append(q, j)
			}
		}
	}
	ans := []int{}
	for i, v := range indeg {
		if v == 0 {
			ans = append(ans, i)
		}
	}
	return ans
}

# Accepted solution for LeetCode #802: Find Eventual Safe States
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        rg = defaultdict(list)
        indeg = [0] * len(graph)
        for i, vs in enumerate(graph):
            for j in vs:
                rg[j].append(i)
            indeg[i] = len(vs)
        q = deque([i for i, v in enumerate(indeg) if v == 0])
        while q:
            i = q.popleft()
            for j in rg[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return [i for i, v in enumerate(indeg) if v == 0]

// Accepted solution for LeetCode #802: Find Eventual Safe States
struct Solution;

impl Solution {
    fn eventual_safe_nodes(graph: Vec<Vec<i32>>) -> Vec<i32> {
        let n = graph.len();
        let mut res = vec![];
        let mut state = vec![0; n];
        for i in 0..n {
            if Self::dfs(i, &mut state, &graph) {
                res.push(i as i32);
            }
        }
        res
    }

    fn dfs(u: usize, state: &mut [i32], graph: &[Vec<i32>]) -> bool {
        match state[u] {
            3 => false,
            2 => true,
            1 => {
                state[u] = 3;
                false
            }
            _ => {
                state[u] = 1;
                let mut s = 2;
                for &v in &graph[u] {
                    if !Self::dfs(v as usize, state, graph) {
                        s = 3;
                    }
                }
                state[u] = s;
                state[u] == 2
            }
        }
    }
}

#[test]
fn test() {
    let graph = vec_vec_i32![[1, 2], [2, 3], [5], [0], [5], [], []];
    let res = vec![2, 4, 5, 6];
    assert_eq!(Solution::eventual_safe_nodes(graph), res);
}

// Accepted solution for LeetCode #802: Find Eventual Safe States
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #802: Find Eventual Safe States
// class Solution {
//     public List<Integer> eventualSafeNodes(int[][] graph) {
//         int n = graph.length;
//         int[] indeg = new int[n];
//         List<Integer>[] rg = new List[n];
//         Arrays.setAll(rg, k -> new ArrayList<>());
//         Deque<Integer> q = new ArrayDeque<>();
//         for (int i = 0; i < n; ++i) {
//             for (int j : graph[i]) {
//                 rg[j].add(i);
//             }
//             indeg[i] = graph[i].length;
//             if (indeg[i] == 0) {
//                 q.offer(i);
//             }
//         }
//         while (!q.isEmpty()) {
//             int i = q.pollFirst();
//             for (int j : rg[i]) {
//                 if (--indeg[j] == 0) {
//                     q.offer(j);
//                 }
//             }
//         }
//         List<Integer> ans = new ArrayList<>();
//         for (int i = 0; i < n; ++i) {
//             if (indeg[i] == 0) {
//                 ans.add(i);
//             }
//         }
//         return ans;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(V + E)

Space

O(V + E)

Approach Breakdown

REPEATED DFS

O(V × E) time

O(V) space

Repeatedly find a vertex with no incoming edges, remove it and its outgoing edges, and repeat. Finding the zero-in-degree vertex scans all V vertices, and we do this V times. Removing edges touches E edges total. Without an in-degree array, this gives O(V × E).

TOPOLOGICAL SORT

O(V + E) time

O(V + E) space

Build an adjacency list (O(V + E)), then either do Kahn's BFS (process each vertex once + each edge once) or DFS (visit each vertex once + each edge once). Both are O(V + E). Space includes the adjacency list (O(V + E)) plus the in-degree array or visited set (O(V)).

Shortcut: Process each vertex once + each edge once → O(V + E). Same as BFS/DFS on a graph.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.