Find Eventual Safe States

MediumGraphs · Topological Sort🧩 Topological Sort LeetCode #802 ↗Updated Oct 30, 2026

Problem

A directed graph with nodes 0..n-1 is given as an adjacency list graph, where graph[i] lists the targets of node i. A node with no outgoing edges is terminal. A node is safe if every walk starting from it is guaranteed to end at a terminal node. Return all safe nodes in ascending order.

Inputgraph = [[1],[2],[],[1,4],[3]]Output[0,1,2]

Inputgraph = [[1,2],[2],[3],[]]Output[0,1,2,3]

Inputgraph = [[0],[0]]Output[]

1 ≤ n ≤ 10⁴ · total edges ≤ 4·10⁴ · graph[i] sorted, distinct · self-loops allowed

Try it yourself

Java

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A node is unsafe exactly when it can reach a cycle. Flip every edge and peel nodes from the terminal end: a node becomes safe once all of its original out-edges lead to already-safe nodes — Kahn's algorithm on out-degrees.

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceFresh Cycle Search From Every Node

Time O(V·(V + E))Space O(V)

For each start node run an independent DFS that tracks which nodes are on the current path. Hitting a node that is already on the path means a cycle is reachable, so the start is unsafe. Nothing is reused between starts.

Java

public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    List<Integer> safe = new ArrayList<>();
    for (int start = 0; start < n; start++) {
        int[] state = new int[n]; // reset for every start: 0 new, 1 on path, 2 done
        if (!reachesCycle(graph, start, state)) safe.add(start);
    }
    return safe;
}

private boolean reachesCycle(int[][] graph, int u, int[] state) {
    if (state[u] == 1) return true;
    if (state[u] == 2) return false;
    state[u] = 1;
    for (int v : graph[u]) {
        if (reachesCycle(graph, v, state)) return true;
    }
    state[u] = 2;
    return false;
}

Obviously correct, but repeats the same exploration up to V times.

BetterMemoised DFS (3-Colour)

Time O(V + E)Space O(V)

Share one colour array across all starts. Grey = on the current path, black = proven safe. A node that meets a grey node stays grey forever, which also marks it unsafe for every later search, so each node and edge is processed once.

Java

public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n]; // 0 white, 1 grey (unsafe/on path), 2 black (safe)
    List<Integer> safe = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (isSafe(graph, i, color)) safe.add(i);
    }
    return safe;
}

private boolean isSafe(int[][] graph, int u, int[] color) {
    if (color[u] != 0) return color[u] == 2;
    color[u] = 1;
    for (int v : graph[u]) {
        if (!isSafe(graph, v, color)) return false; // u stays grey = unsafe
    }
    color[u] = 2;
    return true;
}

Linear and compact, but recursion depth can reach V on long chains.

OptimalKahn's Algorithm on the Reversed Graph

Time O(V + E)Space O(V + E)

Store each node's out-degree and a reversed adjacency list. Terminal nodes (out-degree 0) are safe; when a node is confirmed safe, every predecessor loses one “unresolved” edge. A predecessor whose count hits 0 has only safe exits. Nodes on or leading into a cycle never reach 0.

Java

public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    List<List<Integer>> reversed = new ArrayList<>();
    for (int i = 0; i < n; i++) reversed.add(new ArrayList<>());
    int[] outDegree = new int[n];
    Deque<Integer> queue = new ArrayDeque<>();
    for (int u = 0; u < n; u++) {
        outDegree[u] = graph[u].length;
        for (int v : graph[u]) reversed.get(v).add(u);
        if (outDegree[u] == 0) queue.add(u); // terminal nodes
    }
    boolean[] safe = new boolean[n];
    while (!queue.isEmpty()) {
        int v = queue.poll();
        safe[v] = true;
        for (int u : reversed.get(v)) {
            if (--outDegree[u] == 0) queue.add(u);
        }
    }
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) if (safe[i]) result.add(i);
    return result;
}

Linear, fully iterative (no stack-overflow risk), classic topological peeling.

Pro tip

Collect the answer by scanning 0..n-1 at the end — the queue order is not ascending.

At a glance

Level	Approach	Time	Space
Brute Force	Fresh Cycle Search From Every Node	`O(V·(V + E))`	`O(V)`
Better	Memoised DFS (3-Colour)	`O(V + E)`	`O(V)`
Optimal	Kahn's Algorithm on the Reversed Graph	`O(V + E)`	`O(V + E)`

Common pitfalls

Treating “can reach a terminal” as safe — every path must end.
Using plain visited in DFS — cannot tell a cycle from a node already proven safe.
Forgetting self-loops ([[0]]): node 0 is on a cycle, so it is unsafe.

Interview tips

Restate as “nodes that cannot reach any cycle” — it unlocks both solutions.
Explain why grey nodes left grey are exactly the unsafe ones.
Offer the reversed-graph Kahn version when the interviewer worries about recursion depth.

Pattern

Reverse topological peeling → classify nodes by whether all their outgoing paths terminate (no reachable cycle).

My notes saved in this browser