algoadvance

Leetcode 802. Find Eventual Safe States

Problem Statement

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented by an adjacency list graph where graph[i] is a list of all nodes j for which the edge i -> j exists. 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).

Return an array containing all the eventual safe nodes in ascending order.

Example:

• Input:

  graph = [[1,2],[2,3],[5],[0],[5],[],[]]
  

• Output:

  [2,4,5,6]
  

Clarifying Questions

1. Can the graph contain cycles?
   • Yes, the graph can contain cycles.
2. Are self-loops allowed in the graph?
   • Yes, a node can have a self-loop as it is valid for it to point to itself.
3. Can there be multiple edges between two nodes?
   • No, the graph is given as an adjacency list where each node points to a list of unique nodes.
4. What are the constraints on n?
   • Typically, n will be between 1 and 10^4.

Strategy

We can solve the problem using depth-first search (DFS) combined with a memoization strategy to identify safe nodes. We’ll also use the following state labels to keep track:

• 0: The node has not been visited yet.
• 1: The node is being visited (still in the recursion stack).
• 2: The node is safe (all paths from it lead to a terminal node).
• 3: The node is not safe (it leads to a cycle).

Here’s the approach:

1. Initially, mark all nodes as unvisited (0).
2. Define a DFS function that will traverse from the current node:
   • If the node is in the recursion stack (1), mark it as unsafe (3).
   • If the node is safe (2), no need to process further.
   • Recursively check the connected nodes.
   • If any connected node leads to an unsafe path, then the current node is also unsafe.
   • Otherwise, mark it safe.
3. Collect all nodes marked as safe (2).

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> state(n, 0); // 0: unvisited, 1: visiting, 2: safe, 3: unsafe

        vector<int> result;

        for (int i = 0; i < n; ++i) {
            if (isSafe(i, graph, state)) {
                result.push_back(i);
            }
        }

        return result;
    }

private:
    bool isSafe(int node, vector<vector<int>>& graph, vector<int>& state) {
        if (state[node] != 0) {
            return state[node] == 2;
        }

        state[node] = 1; // Mark node as visiting

        for (int next_node : graph[node]) {
            if (!isSafe(next_node, graph, state)) {
                state[node] = 3; // Mark as unsafe due to unsafe neighbor
                return false;
            }
        }

        state[node] = 2; // Mark as safe
        return true;
    }
};

Time Complexity

• Time Complexity: (O(V + E))
  • Each node and edge is visited at most once.
• Space Complexity: (O(V))
  • Storage for the state vector and recursion stack.

This ensures we efficiently find all eventual safe nodes in the given graph.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?