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.
This approach reframes the problem by looking at it from the perspective of terminal nodes. A node is safe if all its paths lead to a terminal node. This suggests we can work backward from the terminal nodes. The algorithm identifies all nodes that eventually lead to terminal nodes, which are precisely the safe nodes. Nodes involved in cycles or that can reach cycles will never have their out-degrees reduced to zero in this process.
This is effectively performing a topological sort on the graph. We start with nodes that have no outgoing edges (terminal nodes). We then iteratively 'peel off' these safe nodes and update the nodes that point to them. If a node's all outgoing edges point to nodes that have been peeled off, it too becomes safe and is added to our set.
Algorithm
- Reverse the Graph: Create an adjacency list
revGraphthat represents the graph with all its edges reversed. Ifu -> vis an edge in the original graph,v -> uwill be an edge inrevGraph. - Calculate Out-Degrees: Create an array
outDegreeof sizen. Iterate through the originalgraphand for each nodei,outDegree[i]will begraph[i].length. - Initialize Queue: Create a queue and add all terminal nodes from the original graph to it. Terminal nodes are those with an out-degree of 0.
- Process Nodes (Kahn's Algorithm):
a. While the queue is not empty, dequeue a node
u. b. This nodeuis a safe node. Add it to a result list. c. For each neighborvofuinrevGraph(these are the nodes that originally pointed tou): i. DecrementoutDegree[v]. ii. IfoutDegree[v]becomes 0, it means all ofv's outgoing paths now lead to nodes we have processed and confirmed as safe. Therefore,vis also safe. Enqueuev. - Finalize Result: The list of nodes collected during the process contains all safe nodes. Sort this list in ascending order and return it.
Walkthrough
The core idea is to reverse the graph's edges and use a variation of Kahn's algorithm for topological sorting. First, we compute the out-degree of every node in the original graph. All nodes with an out-degree of 0 are terminal nodes and are, by definition, safe. We add them to a queue.
Then, we process the queue. When we dequeue a node u, we know it's safe. We then look at the reversed graph to find all nodes v that had an edge to u. For each such v, we decrement its out-degree. This signifies that one of its outgoing paths has been resolved to a safe conclusion. If v's out-degree drops to 0, it means all of its outgoing paths lead to nodes that are now known to be safe. Thus, v itself becomes a safe node, and we add it to the queue. We continue this until the queue is empty. The nodes that were added to the queue at any point are the safe nodes. Finally, we sort the resulting list.
import java.util.*; class Solution { public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; List<List<Integer>> revGraph = new ArrayList<>(); for (int i = 0; i < n; i++) { revGraph.add(new ArrayList<>()); } int[] outDegree = new int[n]; for (int i = 0; i < n; i++) { outDegree[i] = graph[i].length; for (int neighbor : graph[i]) { revGraph.get(neighbor).add(i); } } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (outDegree[i] == 0) { queue.offer(i); } } List<Integer> safeNodes = new ArrayList<>(); while (!queue.isEmpty()) { int u = queue.poll(); safeNodes.add(u); for (int v : revGraph.get(u)) { outDegree[v]--; if (outDegree[v] == 0) { queue.offer(v); } } } Collections.sort(safeNodes); return safeNodes; }}Complexity
Time
O(N log N + E). Building the reversed graph and initializing out-degrees takes O(N + E). The while loop processes each node and edge once, also taking O(N + E). The final sorting step takes O(N log N). Overall, the complexity is dominated by O(N + E) if E is large, or O(N log N) if E is small.
Space
O(N + E), where N is the number of nodes and E is the number of edges. This space is used for storing the reversed graph (`revGraph`), the `outDegree` array, and the queue.
Trade-offs
Pros
A correct and reasonably efficient approach.
Avoids deep recursion, which can be an issue in some environments.
The logic is closely related to the well-known Kahn's algorithm for topological sorting.
Cons
Requires O(N + E) extra space to store the reversed graph, which can be significant.
Requires a final sorting step, which adds an O(N log N) time component.
This approach identifies safe nodes by finding all nodes that are not unsafe. A node is unsafe if it's part of a cycle or can reach a cycle. We can find all such nodes using a single Depth-First Search (DFS) traversal over the graph, augmented with a 3-state coloring scheme to keep track of the status of each node.
- WHITE (0): The node has not been visited yet.
- GRAY (1): The node is currently being visited (i.e., it's in the current recursion stack).
- BLACK (2): The node and all of its descendants have been visited, and it's confirmed to be a safe node.
If the DFS traversal from a node encounters a GRAY node, it has found a cycle. All nodes in the current recursion path (which are also GRAY) are part of or can reach this cycle, so they are unsafe. A node is marked BLACK only when all paths from it are confirmed to lead to other BLACK nodes or terminal nodes.
Algorithm
- Initialize State: Use a
colorarray of sizento keep track of the state of each node.0(WHITE) for unvisited,1(GRAY) for currently visiting (in the recursion stack), and2(BLACK) for visited and confirmed to be safe. - Iterate and DFS: Iterate through each node
ifrom0ton-1. a. Ifcolor[i]is WHITE (0), it means we haven't determined its safety yet. Start a DFS from this node by calling a helper functionisSafe(i, color, graph). isSafeDFS Helper Function: a. Mark the current node as visiting:color[node] = 1(GRAY). b. For eachneighborof the currentnode: i. Ifcolor[neighbor]is GRAY (1), we've found a back edge to a node in the current recursion path. This means there is a cycle. The current node can reach this cycle, so it's unsafe. Returnfalse. ii. Ifcolor[neighbor]is WHITE (0), recursively callisSafe(neighbor, ...). - If the recursive call returnsfalse, it means the neighbor is part of a cycle or leads to one. Propagate this result by returningfalseimmediately. iii. Ifcolor[neighbor]is BLACK (2), it's a known safe node, so we can safely ignore it and continue to the next neighbor. c. If the loop over neighbors completes without returningfalse, it means the current node does not lead to any cycles. It is a safe node. d. Mark the node as fully explored and safe:color[node] = 2(BLACK). e. Returntrue.- Collect Results: After the main loop finishes, iterate from
0ton-1. Any nodeiwithcolor[i] == 2is a safe node. Add it to the result list. The result will be naturally sorted.
Walkthrough
The algorithm uses a single color array to memoize the state of each node, avoiding redundant computations. We iterate through all nodes. If a node is unvisited (WHITE), we start a DFS from it. The DFS function, isSafe, first marks the current node as visiting (GRAY). Then, it explores its neighbors. If it finds a GRAY neighbor, a cycle is detected, and the node is unsafe. If it finds a WHITE neighbor, it recursively explores it. If the recursive call reveals that the neighbor is unsafe, the current node is also unsafe. If a neighbor is BLACK, we know it's a safe path and continue. If all neighbors are processed without finding an unsafe path, the current node is marked as safe (BLACK). After checking all nodes, we simply collect all nodes marked as BLACK into our result list, which will be sorted because we iterate from 0 to n-1.
import java.util.*; class Solution { public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; // 0: unvisited (WHITE) // 1: visiting (GRAY) // 2: visited and safe (BLACK) int[] color = new int[n]; for (int i = 0; i < n; i++) { if (color[i] == 0) { isSafe(i, graph, color); } } List<Integer> safeNodes = new ArrayList<>(); for (int i = 0; i < n; i++) { if (color[i] == 2) { safeNodes.add(i); } } return safeNodes; } // Returns true if the node is safe, false otherwise private boolean isSafe(int node, int[][] graph, int[] color) { // Mark as visiting color[node] = 1; // GRAY for (int neighbor : graph[node]) { if (color[neighbor] == 1) { // Cycle detected return false; } if (color[neighbor] == 0) { // If neighbor is unvisited, perform DFS. If it's unsafe, this node is also unsafe. if (!isSafe(neighbor, graph, color)) { return false; } } // If color[neighbor] is 2 (BLACK), it's a known safe node, so we continue. } // All paths from this node are safe color[node] = 2; // BLACK return true; }}Complexity
Time
O(N + E), where N is the number of nodes and E is the number of edges. Each node is visited once. During the visit, we iterate through its neighbors. Therefore, every node and every edge is processed a constant number of times.
Space
O(N), where N is the number of nodes. This space is for the `color` array and the recursion stack for DFS.
Trade-offs
Pros
Optimal time complexity of O(N + E).
Optimal space complexity of O(N).
Each node's state is computed only once due to memoization with the color array.
Cons
The concept of three states (colors) can be slightly more complex to understand initially compared to other graph traversal algorithms.
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; }}/** * @param {number[][]} graph * @return {number[]} */ var eventualSafeNodes = function (graph) { const n = graph.length; const color = new Array(n).fill(0); function dfs(i) { if (color[i]) { return color[i] == 2; } color[i] = 1; for (const j of graph[i]) { if (!dfs(j)) { return false; } } color[i] = 2; return true; } let ans = []; for (let i = 0; i < n; ++i) { if (dfs(i)) { ans.push(i); } } return ans; };class Solution {public: vector<int> color; vector<int> eventualSafeNodes(vector<vector<int>> &graph) { int n = graph.size(); color.assign(n, 0); vector<int> ans; for (int i = 0; i < n; ++i) if (dfs(i, graph)) ans.push_back(i); return ans; } bool dfs(int i, vector<vector<int>> &g) { if (color[i]) return color[i] == 2; color[i] = 1; for (int j : g[i]) if (!dfs(j, g)) return false; color[i] = 2; return true; }};class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: def dfs(i): if color[i]: return color[i] == 2 color[i] = 1 for j in graph[i]: if not dfs(j): return False color[i] = 2 return True n = len(graph) color = [0] * n return [i for i in range(n) if dfs(i)]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.