algoadvance

Leetcode 802. Find Eventual Safe States

Problem Statement

Leetcode 802: Find Eventual Safe States

Given a directed graph with n nodes labeled from 0 to n-1, where each node has a list of directed edges to other nodes. Implement a function eventualSafeNodes that returns an array of all the nodes that are eventually safe. A node is eventually safe if, and only if, every possible path starting from that node leads to a terminal node (i.e., a node with no outgoing edges).

Function Signature:

List<Integer> eventualSafeNodes(int[][] graph)

Clarifying Questions

  1. Graph Representation: The graph is given in the form of an adjacency list.
  2. Safe Node Definition: A node is considered safe if it eventually leads to a terminal node on all possible paths.
  3. Cycle Detection: Nodes that are part of cycles are not safe since they don’t lead to terminal nodes on all paths.
  4. Output Order: The result should be returned in sorted order of node indices (ascending order).

Strategy

  1. Graph Traversal and Cycle Detection: Use Depth-First Search (DFS) to detect cycles in the graph.
  2. State Tracking:
    • 0: Node not yet visited.
    • 1: Node is in current path (potential cycle).
    • 2: Node is fully processed and confirmed as safe.
  3. Topological Sorting: By analyzing nodes in reverse (from terminal nodes backward), determine which nodes are safe.
  4. Safe Node Identification: Nodes not part of any cycles or leading indirectly to cycles will be marked safe.

Steps:

  1. Initialize a state array to track the status of each node.
  2. Perform DFS to determine the safety of each node.
  3. Add nodes marked safe to the result list.
  4. Sort and return the result list.

Time Complexity:

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] state = new int[n];
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (dfs(graph, state, i)) {
                result.add(i);
            }
        }
        
        Collections.sort(result);
        return result;
    }
    
    private boolean dfs(int[][] graph, int[] state, int node) {
        if (state[node] != 0) {
            return state[node] == 2; // Return true if node is safe (state 2)
        }
        
        state[node] = 1; // Mark node as visiting (part of the current path)
        for (int next : graph[node]) {
            if (state[next] == 2) continue; // If next node is safe, skip it
            if (state[next] == 1 || !dfs(graph, state, next)) {
                return false; // Found a cycle or a node that leads to a cycle
            }
        }
        
        state[node] = 2; // Mark node as safe
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = // use example above
        System.out.println(sol.eventualSafeNodes(graph)); // Output: [2, 4, 5, 6]
    }
}

Explanation:

  1. Initialization: We initialize the state array and result list.
  2. DFS: We use a DFS function to check whether nodes are safe.
    • A node is marked as visiting (1) when starting the DFS.
    • If a cycle is detected (by reaching a visiting node), the path isn’t safe.
    • If the node leads only to safe nodes or terminal nodes, it’s marked as safe (2).
  3. Result Collection: Nodes identified as safe are added to the result list.
  4. Sorting: The result list is sorted before returning.

This solution efficiently checks and returns the eventual safe nodes in the graph.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI