Coding Interview PatternsFind Eventual Safe States
MediumTopological Sort

Find Eventual Safe States

Explanation & Solution

Practice Problem

Description

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 is a terminal node itself).

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

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

Output:[2,4,5,6]
0
2
1
4
2
5
3
6

Explanation: Nodes 5 and 6 are terminal nodes (no outgoing edges). Node 2 leads to node 5 (safe). Node 4 leads to node 5 (safe). Nodes 0, 1, and 3 are part of a cycle 0 -> 1 -> 3 -> 0, so they are not safe.

Constraints

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

Approach

Topological Sort pattern

1. Build the Reverse Graph

  • For every edge i -> j in the original graph, add edge j -> i in the reverse graph
  • Track the out-degree (number of outgoing edges) for each node in the original graph

2. Initialize BFS from Terminal Nodes

  • Terminal nodes have out-degree 0 — they have no outgoing edges
  • These are guaranteed to be safe, so add them to the BFS queue

3. Reverse BFS (Topological Sort)

  • Process nodes from the queue one by one
  • Mark each processed node as safe
  • For each predecessor in the reverse graph, decrement its out-degree
  • If a predecessor's out-degree reaches 0, all its outgoing edges lead to safe nodes, so it is also safe — add it to the queue

4. Collect Results

  • Iterate through all nodes from 0 to n - 1
  • Add nodes marked as safe to the result array
  • This naturally produces the result in ascending order

Key Insight

  • A node is safe if and only if it is not part of a cycle and does not lead to any cycle
  • By reversing the graph and doing BFS from terminal nodes, we effectively perform a reverse topological sort — peeling off safe nodes layer by layer
  • When a node's out-degree reaches 0, all paths from it lead to already-confirmed safe nodes
Time
O(V + E) where V is the number of nodes and E is the number of edges
Space
O(V + E) for the reverse graph

Visualization

Input:
BFS Traversal7 nodes, 7 edges
0123456
output—

Press play to start bfs traversal

CurrentQueuedVisited
14 steps

Solution Code

Previous
Sort Items by Groups Respecting Dependencies
Next
Course Schedule IV