Skip to content

← leetcode

Find Eventual Safe States

· Medium

LeetCode problem 802

My approach to this question was to use depth-first search. After running through the example test-cases, I came to the realisation that all nodes that either point to or exist in a cycle are unsafe (since if you keep on cycling through the loop, then you will never reach a terminal node).

Therefore, when we use DFS on every node (have to visit every edge to be able to determine which nodes are safe), we will have to maintain a runtime stack, to check what nodes you have seen inside the current recursive call, and a seen array, to check what nodes you have seen before (inside & outside of the current recursive call).

Then,

  • if the runtime stack detects that I have seen the node before, it tells me that there is a cycle inside this branch, meaning every previous node we traversed is unsafe. We then return from the recursive function call early, so that in the runtime stack, each traversed node retains their seen value, meaning if any of these nodes were to be traversed in another DFS run, the runtime stack would continue to detect a cycle
  • else, if the seen array detects that I have seen the node before (and the runtime stack does not), then it implies that this node is safe, meaning the DFS function would return that the branch is safe.

Finally, since we run DFS on every node, we will get a boolean value determining whether or not each node is safe or not and can just group these values into an array to return as our ans.

code

class Solution {
public:
    int dfs (int index, vector<vector<int>> &graph, vector<int> &stack, vector<int> &seen) {
        if (stack[index] == 1) {
            return 1;
        }

        if (seen[index] == 1) {
            return 0;
        }

        stack[index] = 1;
        seen[index] = 1;

        for (auto &node : graph[index]) {
            if (dfs(node, graph, stack, seen)) {
                return 1;
            }
        }

        stack[index] = 0;
        return 0;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> stack (graph.size(), 0);
        vector<int> seen (graph.size(), 0);

        vector<int> ans;
        for (int i = 0; i < graph.size(); ++i) {
            if(!dfs(i, graph, stack, seen)) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

complexity

  • Time: O(m+n) (where n is the number of nodes and m is the number of edges in the graph)
  • Space: O(n)