Watch 10 video solutions for Find Eventual Safe States, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by take U forward has 291,747 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= n <= 1040 <= graph[i].length <= n0 <= graph[i][j] <= n - 1graph[i] is sorted in a strictly increasing order.[1, 4 * 104].Problem Overview: You are given a directed graph where graph[i] lists all nodes reachable from node i. A node is considered eventually safe if every possible path starting from it ends at a terminal node (a node with no outgoing edges). Any node that can reach a cycle is unsafe. The task is to return all safe nodes in sorted order.
Approach 1: Reverse Graph and Topological Sort (O(V + E) time, O(V + E) space)
This approach converts the problem into a reverse topological process. First build the reverse graph so that every edge u → v becomes v → u. At the same time track the outdegree of each node in the original graph. Terminal nodes naturally have outdegree 0, so they are guaranteed safe. Push them into a queue and process them using a BFS-style topological sort. Every time you remove a safe node, decrease the outdegree of its predecessors in the reverse graph. If a predecessor’s outdegree becomes 0, it also becomes safe and enters the queue. The key insight: nodes that eventually lead only to safe nodes will lose all outgoing edges during this process. This solution is essentially a reversed topological sort applied to a graph, making it highly efficient and easy to reason about.
Approach 2: Depth-First Search with Safe Node Identification (O(V + E) time, O(V) space)
This method uses DFS to detect cycles and classify nodes. Maintain a state array with three states: unvisited, visiting, and safe. During DFS, mark the node as visiting. If you encounter another visiting node, a cycle exists and the path is unsafe. If all neighbors eventually lead to safe nodes, mark the current node as safe and return true. Memoization ensures each node is processed once. This is a classic cycle-detection pattern using Depth-First Search. The algorithm avoids recomputation by caching node states, giving linear complexity relative to nodes and edges.
Recommended for interviews: The reverse graph + topological sort solution is typically preferred. It clearly models the problem as eliminating nodes that cannot participate in cycles, and the BFS queue naturally reveals safe nodes. Interviewers often expect you to recognize the connection between cycle detection and topological processing. The DFS approach is also valid and demonstrates strong understanding of recursion and graph state tracking, but the topological strategy tends to be easier to explain and reason about under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Graph + Topological Sort (BFS) | O(V + E) | O(V + E) | Best general solution. Efficient for detecting nodes not connected to cycles in directed graphs. |
| DFS with Safe Node Memoization | O(V + E) | O(V) | Useful when implementing recursive cycle detection or when DFS is already part of the solution. |