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.
This approach utilizes the concept of reversing the graph and then performing a topological sort. Essentially, if we consider nodes leading to terminal nodes in the original graph, these nodes can be treated as terminal nodes in the reversed graph. We perform a topological sort to find such nodes.
By processing nodes which have no outgoing edges in the reversed graph (these correspond to safe nodes in the original graph), we can iteratively determine more nodes that are safe.
The function findEventualSafeNodes reverses the input graph and employs a topological sorting method to determine the safe nodes.
For simplicity, you will need to manage node degrees and process the graph using a queue (BFS style). Nodes that have no incoming edges left are safe.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal.
Space Complexity: O(V) for storing the reversed graph and the in-degrees array.
This approach adopts a classic depth-first search (DFS) to identify which nodes are safe. Safe nodes are marked during traversal.
We maintain a visited state for each node: unvisited, visiting, or safe. During DFS traversal, if we encounter a node marked as visiting, a cycle is detected, and the path is unsafe.
The function leverages DFS to maintain a status for each node: safe, unsafe, or unknown. It handles cycles efficiently by marking nodes actively being visited and recording safe nodes on successful completion of DFS for a node.
C++
C#
JavaScript
Time Complexity: O(V + E), as each node and each edge is examined only once.
Space Complexity: O(V) for the recursion stack and state storage.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Graph and Topological Sort | Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is due to the graph traversal. Space Complexity: O(V) for storing the reversed graph and the in-degrees array. |
| Approach 2: Depth-First Search with Safe Node Identification | Time Complexity: O(V + E), as each node and each edge is examined only once. Space Complexity: O(V) for the recursion stack and state storage. |
| Default Approach | — |
| 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. |
G-20. Find Eventual Safe States - DFS • take U forward • 291,747 views views
Watch 9 more video solutions →Practice Find Eventual Safe States with our built-in code editor and test cases.
Practice on FleetCode