medium Find Eventual Safe States

Problem Statement

You are given a directed graph with n nodes, labeled from 0 to n-1. This graph is described by a 2D integer array graph, where graph[i] is an array of nodes adjacent to node i, indicating there is a directed edge from node i to each of the nodes in graph[i].

A node is called a terminal node if it has no outgoing edges. A node is considered safe if every path starting from that node leads to a terminal node (or another safe node).

Return an array of all safe nodes in ascending order.

Examples

Example 1:

• Input: graph = [[1,2],[2,3],[2],[],[5],[6],[]]

• Expected Output: [3,4,5,6]
• Explanation:
  • Node 3 is a terminal node.
  • Node 4 leads to node 5, which is a safe node.
  • Node 5 leads to node 6, which is a terminal node.
  • Node 6 is a terminal node.

Example 2:

• Input: graph = [[1,2],[2,3],[5],[0],[],[],[4]]

• Expected Output: [2,4,5,6]
• Explanation:
  • Node 2 leads to node 5, which is a terminal node.
  • Node 4 is a terminal node.
  • Node 5 is a terminal node.
  • Node 6 leads to node 4, which is a terminal node.

Example 3:

• Input: graph = [[1,2,3],[2,3],[3],[],[0,1,2]]

• Expected Output: [0,1,2,3,4]
• Explanation:
  • Node 3 is a terminal node.
  • Node 2 leads to node 3, which is a terminal node.
  • Node 1 leads to node 2, which is a safe node, and node 3, which is a terminal node.
  • Similarly, all node leads to either a terminal or a safe node.

Constraints:

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[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 * 10⁴].

Solution

To solve this problem, we will use a depth-first search (DFS) approach to explore each node and its connections. We'll mark nodes as "safe" or "unsafe" based on whether all paths from the node lead to terminal nodes. This is efficient because we can mark nodes during the DFS traversal and avoid reprocessing them.

This approach works well because we only visit each node a limited number of times, leading to an overall efficient solution. By marking nodes as we determine their status, we avoid unnecessary re-computation. This is particularly useful for graphs, where cycles and repeated paths are common.

Step-by-Step Algorithm

1. Initialize variables:

   • Create an array visited of size n (number of nodes) and set all elements to 0. This array keeps track of the state of each node: 0 means unvisited, 1 means visiting, and -1 means safe.
   • Create an empty list result to store the safe nodes.

2. Define a DFS function:

   • If the current node is marked as safe (-1), return True.
   • If the current node is marked as visiting (1), return False to indicate a cycle.
   • Mark the current node as visiting (1).
   • Iterate through all adjacent nodes of the current node:
     • Recursively call the DFS function on each adjacent node.
     • If any adjacent node returns False, mark the current node as unsafe and return False.
   • Mark the current node as safe (-1).
   • Return True to indicate the current node is safe.

3. Process each node:

   • Iterate through each node from 0 to n-1.
   • For each node, call the DFS function. If the function returns True, add the node to the result list.

4. Sort and return the result:

   • Sort the result list in ascending order.
   • Return the result list.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step using the graph [[1,2],[2,3],[2],[],[5],[6],[]]:

Graph representation:

• Node 0 -> [1, 2]
• Node 1 -> [2, 3]
• Node 2 -> [2]
• Node 3 -> []
• Node 4 -> [5]
• Node 5 -> [6]
• Node 6 -> []

Initial state:

• visited = [0, 0, 0, 0, 0, 0, 0]
• result = []

Step-by-step DFS calls:

1. Processing node 0:

   • DFS(0) is called.
   • visited[0] is marked as 1.
   • Processing adjacent node 1 of node 0:
     • DFS(1) is called.
     • visited[1] is marked as 1.
     • Processing adjacent node 2 of node 1:
       • DFS(2) is called.
       • visited[2] is marked as 1.
       • Processing adjacent node 2 of node 2:
         • DFS(2) is called.
         • visited[2] is already 1 (cycle detected).
         • Return False.
       • visited[2] remains 1 (unsafe).
       • Return False.
     • visited[1] remains 1 (unsafe).
     • Return False.
   • visited[0] remains 1 (unsafe).
   • Return False.

2. Processing node 1:

   • DFS(1) is called.
   • visited[1] is already 1 (unsafe).
   • Return False.

3. Processing node 2:

   • DFS(2) is called.
   • visited[2] is already 1 (unsafe).
   • Return False.

4. Processing node 3:

   • DFS(3) is called.
   • visited[3] is marked as 1.
   • Node 3 has no adjacent nodes.
   • visited[3] is marked as -1 (safe).
   • Add node 3 to result.
   • result = [3]
   • Return True.

5. Processing node 4:

   • DFS(4) is called.
   • visited[4] is marked as 1.
   • Processing adjacent node 5 of node 4:
     • DFS(5) is called.
     • visited[5] is marked as 1.
     • Processing adjacent node 6 of node 5:
       • DFS(6) is called.
       • visited[6] is marked as 1.
       • Node 6 has no adjacent nodes.
       • visited[6] is marked as -1 (safe).
       • Add node 6 to result.
       • result = [3, 6]
       • Return True.
     • visited[5] is marked as -1 (safe).
     • Add node 5 to result.
     • result = [3, 6, 5]
     • Return True.
   • visited[4] is marked as -1 (safe).
   • Add node 4 to result.
   • result = [3, 6, 5, 4]
   • Return True.

6. Processing node 5:

   • DFS(5) is called.
   • visited[5] is already -1 (safe).
   • Return True.

7. Processing node 6:

   • DFS(6) is called.
   • visited[6] is already -1 (safe).
   • Return True.

Final result:

• Sort result = [3, 4, 5, 6]
• Return [3, 4, 5, 6]

Code

import java.util.*;

public class Solution {

  public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;
    int[] visited = new int[n]; // 0: unvisited, 1: visiting, -1: safe
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < n; i++) {
      if (dfs(graph, visited, i)) {
        result.add(i);
      }
    }

    Collections.sort(result); // Sorting the result
    return result;
  }

  private boolean dfs(int[][] graph, int[] visited, int node) {
    if (visited[node] == -1) return true; // If node is marked as safe
    if (visited[node] == 1) return false; // If node is part of a cycle

    visited[node] = 1; // Mark the node as visiting
    for (int next : graph[node]) {
      if (!dfs(graph, visited, next)) {
        return false; // If any adjacent node is not safe
      }
    }

    visited[node] = -1; // Mark the node as safe
    return true;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.eventualSafeNodes(
        new int[][] { { 1, 2 }, { 2, 3 }, { 2 }, {}, { 5 }, { 6 }, {} }
      )
    );
    System.out.println(
      sol.eventualSafeNodes(
        new int[][] { { 1, 2 }, { 2, 3 }, { 5 }, { 0 }, {}, {}, { 4 } }
      )
    );
    System.out.println(
      sol.eventualSafeNodes(
        new int[][] { { 1, 2, 3 }, { 2, 3 }, { 3 }, {}, { 0, 1, 2 } }
      )
    );
  }
}

Complexity Analysis

Time Complexity

• The time complexity of the algorithm is , where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because each node and each edge are processed once in the depth-first search (DFS).

Space Complexity

• The space complexity of the algorithm is , where V is the number of vertices. This is due to the space required to store the visited array and the recursion stack during the DFS.