Skip to main content
DSA patterns

Find Eventual Safe States

mediumGraphs Must-doGoogleAmazonCisco

Problem statement

You're given a directed graph of n nodes, numbered 0 to n - 1. graph[i] lists the nodes that node i has a direct edge to. A node with no outgoing edges is a terminal node. A node is safe if every path you can take starting from it is guaranteed to end at a terminal node — in other words, no matter which outgoing edge you follow at each step, you can never get stuck looping forever. Return every safe node, sorted in ascending order.

This is the shape of a dependency-cycle check: think of each node as a job, deploy step, or service that can trigger others. A "safe" node is one where triggering it can never lead back into an infinite retry loop — every chain it starts eventually bottoms out cleanly.

Examples

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

Explanation: Nodes 5 and 6 have no outgoing edges, so they're terminal (and therefore safe). Node 2 only leads to node 5, node 4 only leads to node 5 — both safe. Node 3 leads back to node 0, and node 0 and node 1 both eventually loop back into that cycle (0 → 1 → 3 → 0), so 0, 1, and 3 are unsafe.

Example 1

Example 2

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

Output: [4]

Explanation: Node 4 has no outgoing edges, so it's the only terminal node. Every other node either sits in a cycle or can reach one — node 3 leads back to node 0, which starts the cycle again — so nothing else is safe.

Hints

Hint 1: A node with no outgoing edges is always safe by definition — start your reasoning from there.

Approach

Optimal: Reversed graph, peeling from the terminal nodes inward

Intuition

Flip the question around. Instead of asking "does every path out of this node reach a terminal node," ask it from the other direction: a node is safe exactly when it can only ever reach terminal or already-confirmed-safe nodes. So start at the terminal nodes — those are safe by definition — and work backward: any node whose every outgoing edge points at an already-confirmed-safe node must itself be safe.

This is Kahn's-style topological peeling, but run on the reverse graph. Build a reverse adjacency list (callers[v] = nodes with an edge into v), and track each node's out-degree (how many outgoing edges it still has left to resolve). Every time a node is confirmed safe, walk its callers and decrement their out-degree; once a caller's out-degree hits zero, every one of its outgoing edges has been resolved safe, so it's safe too, and it gets queued for its own callers to process.

Steps

  1. Build outDegree[node], the number of outgoing edges each node has, straight from the input.
  2. Build a reversed adjacency list callers[node]: for every edge u → v in the original graph, record u in callers[v].
  3. Put every node with outDegree == 0 (the terminal nodes) in a queue and mark it safe.
  4. While the queue isn't empty: pop a safe node, and for each of its callers, decrement that caller's outDegree. If a caller's outDegree just hit 0, mark it safe and add it to the queue.
  5. Once the queue is empty, collect every node marked safe, in order — that's already sorted since you built the state array by index.

Dry run

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

Initial out-degrees: [4, 2, 2, 2, 0]. Reversed edges (callers): callers[1]=[0], callers[2]=[0,1], callers[3]=[0,2], callers[4]=[0,2,3], callers[0]=[3].

step queue action
start [4] node 4 has out-degree 0 → safe, queued
pop 4 [] decrement callers of 4 (nodes 0, 2, 3): out-degrees become [3, 2, 1, 1, -] — none hit 0 yet

No other node's out-degree reaches zero — nodes 0, 1, 2, and 3 all still have at least one edge that hasn't been resolved safe (they're all tangled in the 0 → 3 → 0 cycle, plus 1 and 2 feeding into it). Final safe set: [4] — matches the example.

Edge cases: a node with a self-loop never has its out-degree fully cleared by this process (one of its own edges points at itself, which can only clear once it's already safe — a contradiction), so it correctly stays unsafe. A graph where every node is terminal marks every node safe on the first pass.

Complexity

Time O(V + E)

Space O(V + E)

from collections import deque

class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        n = len(graph)
        out_degree = [len(neighbors) for neighbors in graph]
        callers = [[] for _ in range(n)]  # reversed edges: callers[v] = nodes that point to v
        for node, neighbors in enumerate(graph):
            for nei in neighbors:
                callers[nei].append(node)

        q = deque(node for node in range(n) if out_degree[node] == 0)
        safe = [False] * n
        for node in q:
            safe[node] = True

        while q:
            node = q.popleft()
            for caller in callers[node]:
                out_degree[caller] -= 1
                if out_degree[caller] == 0:
                    safe[caller] = True
                    q.append(caller)

        return [node for node in range(n) if safe[node]]


if __name__ == "__main__":
    print(Solution().eventualSafeNodes([[1, 2], [2, 3], [5], [0], [5], [], []]))
    print(Solution().eventualSafeNodes([[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "every path from this node must reach a terminal / dead-end node" — that's asking which nodes are cycle-free, not just whether a cycle exists
  • Idea: either DFS with a three-state (unvisited / in-progress / resolved) marker to catch back-edges, or peel inward from terminal nodes on the reversed graph using out-degree, Kahn's-style
  • Cost: O(V + E) time and space either way — each node and edge is processed a constant number of times
  • Trap: using only a plain visited/unvisited boolean — it can't distinguish "still being explored" (a real cycle) from "already fully resolved" (safe to reuse)

Interview follow-ups

  • The graph updates frequently (edges are added or removed between queries). How would you avoid recomputing everything each time?

    Adding an edge can only ever turn a safe node unsafe (never the reverse), so after an edge addition you only need to re-check whether the new edge's destination is unsafe, and if so, propagate that unsafety backward to anything that now depends on it — you don't need to recheck nodes that were already confirmed unsafe, or nodes with no path to the change. Removing an edge is trickier: a node that was unsafe purely because of that one cycle might now become safe, which generally requires recomputing the affected region from scratch, since "becoming safe" isn't a property you can propagate incrementally the same way.

  • How would you report *why* a node is unsafe — for example, which cycle it's caught in?

    During the DFS approach, keep a parent-pointer chain of the current path. The moment you detect a back-edge into a node still marked "in progress," walk the path backward from the current node to that ancestor — everything in between is the cycle itself. This adds no real cost beyond storing the current path (O(V) extra space), since you're already implicitly tracking it via the call stack.

  • What if the graph could have millions of nodes and needed to run on a single machine with limited memory?

    The reversed-graph approach's memory cost is dominated by the reverse adjacency list, which is the same size as the original edge list — so it doesn't inherently cost more than storing the graph itself. If even that is too much, you can avoid materializing callers up front by doing a single extra pass over the original edge list each time you need to find a node's callers, trading a higher constant-factor runtime for a smaller memory footprint.

Frequently asked questions

A plain visited set only tells you "I've seen this node before," not "I'm still in the middle of exploring it." Those are different things: a node fully resolved as safe was also "seen before," but revisiting it isn't a problem — you just reuse the answer. Only revisiting a node that's still mid-exploration (an ancestor on the current path) signals an actual cycle. That's why the three-state version — unvisited, in-progress, resolved — is necessary, not just a nice-to-have.

Because it sidesteps cycle detection entirely. Nodes stuck in a cycle simply never have their out-degree reach zero — they always have at least one un-resolved outgoing edge feeding back into the cycle — so they're silently left out of the "safe" set without the algorithm ever needing to explicitly notice "this is a cycle." It's an elegant way to get the same answer by only ever reasoning forward from what's already known to be safe.

Both run in O(V + E) time and space, so asymptotically they're identical. The DFS version is usually more intuitive to write from scratch in an interview since it mirrors how you'd reason about the problem out loud. The reversed-graph version avoids recursion (useful if the graph is large enough that deep recursion risks a stack overflow) and is the more natural fit if you're already comfortable with topological-sort-style peeling.

This is exactly the shape of validating a dependency graph before it runs — build steps, service startup order, or config includes that reference each other. A "safe" node here is one that's guaranteed to terminate cleanly; an "unsafe" one is a node caught in a circular dependency that would hang or infinitely retry. Being able to flag every node affected by a cycle, not just detect that a cycle exists somewhere, is the more useful real-world version of cycle detection.

Course Schedule only asks "does a cycle exist anywhere in the graph" — a single yes/no. This problem asks "which specific nodes are affected by a cycle," including nodes that aren't part of a cycle themselves but can still reach one. That's a strictly more detailed answer, and it's why the DFS here needs a per-node memoized result instead of a single global "cycle found" flag.