How do you solve Find Eventual Safe States on LeetCode?

Find Eventual Safe States (LeetCode #802) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + e) time complexity and O(n) space complexity. Key insight: Understanding terminal nodes is crucial to finding safe nodes.

What is the brute force solution for Find Eventual Safe States?

The brute force approach for Find Eventual Safe States is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every node and explores all paths from that node to see if they lead to a terminal node. If all paths lead to terminal nodes, then the node is safe. The optimal Optimal Solution approach improves this to O(n + e).

What are the interview tips for Find Eventual Safe States?

Clarify the definition of safe nodes before starting. Think about edge cases like self-loops or disconnected graphs. Explain your thought process clearly while coding.

What are common mistakes when solving Find Eventual Safe States?

Failing to handle cycles correctly. Not considering all paths from a node.

#802

Find Eventual Safe States

Medium

Depth-First SearchBreadth-First SearchGraph TheoryTopological SortGraph TraversalTopological Sort

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + e)
Space	O(1)	O(n)

💡

Intuition

Time O(n + e)Space O(n)

The optimal solution uses a reverse graph approach and topological sorting. By identifying terminal nodes first and working backwards, we can efficiently determine which nodes are safe.

⚙️

Algorithm

3 steps

1Step 1: Create a reverse graph where edges point to the source nodes.
2Step 2: Identify terminal nodes and initialize a queue with them.
3Step 3: Perform a topological sort by removing nodes from the queue and marking their predecessors as safe if all their outgoing edges lead to safe nodes.

solution.py24 lines

1# Full working Python code
2from collections import defaultdict, deque
3
4def eventualSafeNodes(graph: List[List[int]]) -> List[int]:
5    n = len(graph)
6    reverse_graph = defaultdict(list)
7    out_degree = [0] * n
8    for node in range(n):
9        out_degree[node] = len(graph[node])
10        for neighbor in graph[node]:
11            reverse_graph[neighbor].append(node)
12    queue = deque()
13    for node in range(n):
14        if out_degree[node] == 0:
15            queue.append(node)
16    safe = []
17    while queue:
18        node = queue.popleft()
19        safe.append(node)
20        for predecessor in reverse_graph[node]:
21            out_degree[predecessor] -= 1
22            if out_degree[predecessor] == 0:
23                queue.append(predecessor)
24    return sorted(safe)

ℹ

Complexity note: The time complexity is O(n + e) where n is the number of nodes and e is the number of edges, as we traverse each node and edge once. The space complexity is O(n) for storing the reverse graph and out-degree counts.

1Understanding terminal nodes is crucial to finding safe nodes.
2Using reverse graphs simplifies the problem of tracking paths.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.