LeetCode 802: Find Eventual Safe States Solution

Master LeetCode problem 802 (Find Eventual Safe States), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

802. Find Eventual Safe States

Medium

Depth-First Search Breadth-First Search Graph Topological Sort

Problem Explanation

Explanation

To solve this problem, we can use the concept of detecting cycles in a directed graph. We will perform a depth-first search (DFS) traversal on the graph starting from each node. If we encounter a cycle during the traversal, then the current node and all its descendants are not safe. Otherwise, if we reach a terminal node or a node that has already been marked safe during the traversal, then the current node is safe.

We will mark nodes as one of the following:

0 - unvisited
1 - currently visiting (part of the current DFS traversal)
2 - safe

At the end of the algorithm, the nodes marked as safe will be added to the result array.

Time Complexity: O(N + E) where N is the number of nodes and E is the number of edges in the graph. Space Complexity: O(N) where N is the number of nodes.

Solution Code

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> result = new ArrayList<>();
        int n = graph.length;
        int[] state = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (isSafeNode(i, graph, state)) {
                result.add(i);
            }
        }
        
        return result;
    }
    
    private boolean isSafeNode(int node, int[][] graph, int[] state) {
        if (state[node] != 0) {
            return state[node] == 2;
        }
        
        state[node] = 1;
        for (int neighbor : graph[node]) {
            if (!isSafeNode(neighbor, graph, state)) {
                return false;
            }
        }
        
        state[node] = 2;
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 802 (Find Eventual Safe States)?

This page provides optimized solutions for LeetCode problem 802 (Find Eventual Safe States) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 802 (Find Eventual Safe States)?

The time complexity for LeetCode 802 (Find Eventual Safe States) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 802 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 802 in Java, C++, or Python.

Back to LeetCode Solutions