#802 Find Eventual Safe States

frequently reported atAmazon Google

the problem

In plain words

graph[i] lists the nodes node i points to. A terminal node has no outgoing edges. A node is safe if every path from it ends at a terminal node. Return all safe nodes in ascending order.

in graph = [[1,2],[2,3],[5],[0],[5],[],[]]

out [2,4,5,6]

0, 1, 3 can loop 0→1→3→0 forever.

in graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

out [4]

1 ≤ n ≤ 10⁴
0 ≤ graph[i].length ≤ n
graph[i] is strictly increasing
Total edges ≤ 4·10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTopological sort & cycle detection

Unsafe = can reach a cycle. In DFS colours, a vertex is safe exactly when it turns black; anything left gray touched a cycle.

solutions

From brute force to optimal

Reuse cycle-detection DFS: a node is safe iff all its neighbours are safe; meeting a gray node means a cycle.

isSafe(u): if coloured, return colour == black.
Paint gray; if any neighbour is unsafe, return false (u stays gray).
Paint black, return true.
Collect safe nodes in index order.

timeO(V + E)

Each node is resolved once thanks to the colour memo.

spaceO(V)

Colour array plus recursion depth up to V.

javajava.util.*

1class Solution {2    public List<Integer> eventualSafeNodes(int[][] graph) {3        int n = graph.length;4        int[] color = new int[n]; // 0 unvisited, 1 visiting (on path), 2 safe5        List<Integer> safe = new ArrayList<>();6        for (int v = 0; v < n; v++) if (isSafe(v, graph, color)) safe.add(v); // ascending for free7        return safe;8    }9 10    private boolean isSafe(int u, int[][] graph, int[] color) {11        if (color[u] != 0) return color[u] == 2; // gray = on a cycle (or leads into one)12        color[u] = 1;13        for (int v : graph[u]) {14            if (!isSafe(v, graph, color)) return false; // u stays gray forever = unsafe15        }16        color[u] = 2;17        return true;18    }19}

Flip every edge. Terminal nodes become sources. A node is safe once all of its original exits are known safe.

Reverse edges; outdegree[u] = graph[u].length.
Queue nodes with outdegree 0 (terminal).
Pop v (safe); for each u pointing to v, decrement outdegree[u]; enqueue at 0.
Return safe nodes ascending.

timeO(V + E)

Each reversed edge is processed once.

spaceO(V + E)

The reversed adjacency list.

javajava.util.*

1class Solution {2    public List<Integer> eventualSafeNodes(int[][] graph) {3        int n = graph.length;4        List<List<Integer>> reverse = new ArrayList<>();5        for (int i = 0; i < n; i++) reverse.add(new ArrayList<>());6        int[] outdegree = new int[n];7        for (int u = 0; u < n; u++) {8            outdegree[u] = graph[u].length;9            for (int v : graph[u]) reverse.get(v).add(u); // flip every edge10        }11        Deque<Integer> queue = new ArrayDeque<>();12        for (int v = 0; v < n; v++) if (outdegree[v] == 0) queue.offer(v); // terminal nodes13        boolean[] safe = new boolean[n];14        while (!queue.isEmpty()) {15            int v = queue.poll();16            safe[v] = true;17            for (int u : reverse.get(v)) {18                if (--outdegree[u] == 0) queue.offer(u); // all of u's exits are safe now19            }20        }21        List<Integer> result = new ArrayList<>();22        for (int v = 0; v < n; v++) if (safe[v]) result.add(v);23        return result;24    }25}

in the room

How to say it in the interview

talk track

Translate: "safe" means no path reaches a cycle. Then either reuse colour DFS or run Kahn backwards from the terminals.

traps

Resetting gray nodes to white after a failed DFS — they must stay gray (unsafe) so later lookups are O(1) and correct.

what they ask next

Follow-ups

A path of 10⁴ nodes could make the DFS 10⁴ calls deep. How do you avoid that?

Use the reversed-graph Kahn version: it is a plain loop with a queue, so there is no recursion at all. Same O(V + E).

Return the unsafe nodes instead?

They are the complement: the nodes left gray after the DFS, or the nodes Kahn never dequeues on the reversed graph.

before you submit

Edge cases to test

A self-loop makes that node unsafe.
A terminal node (no outgoing edges) is safe.
A node with one edge to a terminal and one into a cycle is unsafe — every path must end.

practise next