Find Eventual Safe States
MedPrompt
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.- The graph may contain self-loops.
- The number of edges in the graph will be in the range
[1, 4 * 104].
Approaches
3 approaches with complexity analysis and trade-offs.
This approach checks each node one by one to determine if it's a safe state. For every node, it initiates a new Depth-First Search (DFS) to explore all possible paths starting from it. During the DFS, it keeps track of the nodes in the current path to detect cycles. If a path encounters a node that is already in the current path, a cycle is found, and the starting node is deemed unsafe. If all paths from the starting node end in terminal nodes, it's considered safe. The main drawback is the massive amount of redundant computation, as the safety of a node might be re-evaluated multiple times across different initial DFS calls.
Algorithm
- Iterate through each node
ifrom0ton-1to check if it's a safe node. - For each node
i, start a Depth-First Search (DFS). To do this, call a helper function, sayisSafe(currentNode, path). Thepathparameter is a set that keeps track of all nodes in the current traversal path from the starting nodeitocurrentNode. - Inside the
isSafefunction: a. IfcurrentNodeis already inpath, it means we have detected a cycle. A node in a cycle is not safe. Returnfalse. b. IfcurrentNodeis a terminal node (no outgoing edges), it's safe by definition. Returntrue. c. AddcurrentNodeto thepathset to mark it as part of the current recursion stack. d. Recursively callisSafefor all neighbors ofcurrentNode. If any of these recursive calls returnfalse, it meanscurrentNodecan lead to an unsafe path. Immediately returnfalse. e. If all neighbors lead to safe paths, thencurrentNodeis safe. Before returning, removecurrentNodefrompath(backtracking). f. Returntrue. - If the initial call
isSafe(i, new HashSet<>())returnstrue, addito the list of safe nodes. - After checking all nodes, return the list of safe nodes.
Walkthrough
The algorithm iterates through every node in the graph and, for each one, performs a full DFS traversal to verify its safety. A helper function, isSafe(node, path), is used for this purpose. The path set is crucial for detecting cycles within a single traversal. If the DFS for a node u encounters a neighbor v that is already in the path, it signifies a cycle, making u unsafe. If a neighbor v is found to be unsafe through a recursive call, u is also marked as unsafe. A node is only safe if all its outgoing paths exclusively lead to terminal nodes. Because this method doesn't use memoization, the safety status of a single node might be computed over and over again if it's reachable from multiple starting nodes, leading to an exponential time complexity in the worst-case scenarios.
import java.util.*; class Solution { public List<Integer> eventualSafeNodes(int[][] graph) { List<Integer> safeNodes = new ArrayList<>(); for (int i = 0; i < graph.length; i++) { if (isSafe(i, graph, new HashSet<>())) { safeNodes.add(i); } } return safeNodes; } private boolean isSafe(int node, int[][] graph, Set<Integer> path) { if (path.contains(node)) { // Cycle detected return false; } if (graph[node].length == 0) { // Terminal node return true; } path.add(node); for (int neighbor : graph[node]) { if (!isSafe(neighbor, graph, path)) { // Path to an unsafe node or cycle path.remove(node); // Backtrack return false; } } path.remove(node); // Backtrack return true; }}Complexity
Time
O(N * (N + E)) in a graph with no sharing of paths, but can be as bad as O(N * N!) in graphs with many paths. This is because for each of the N nodes, we might traverse a significant portion of the graph, leading to repeated work. For instance, in a dense DAG, the number of paths can be exponential.
Space
O(N), where N is the number of nodes. This is for the recursion stack depth and the `path` set, which can store up to N nodes in the case of a long path.
Trade-offs
Pros
Conceptually simple and a direct translation of the problem definition.
Cons
Extremely inefficient due to re-computation.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution {private int[] color;private int[][] g;public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; color = new int[n]; g = graph; List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (dfs(i)) { ans.add(i); } } return ans; }private boolean dfs(int i) { if (color[i] > 0) { return color[i] == 2; } color[i] = 1; for (int j : g[i]) { if (!dfs(j)) { return false; } } color[i] = 2; return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.