Find Eventual Safe States

Find Eventual Safe States

What is this problem about?

In the Find Eventual Safe States interview question, you are given a directed graph where nodes are indexed from 0 to n-1. A node is considered "safe" if every possible path starting from that node eventually leads to a terminal node (a node with no outgoing edges). Your goal is to return a list of all safe nodes in ascending order. This Find Eventual Safe States coding problem is essentially about identifying nodes that cannot reach a cycle.

Why is this asked in interviews?

Companies like Uber, Microsoft, and Google use this problem to test a candidate's understanding of Cycle Detection and Topological Sort. It requires more than just a simple graph traversal; it requires identifying "toxic" components (cycles) and understanding how that toxicity propagates backward through the graph. It evaluations your proficiency with graph coloring or dependency resolution.

Algorithmic pattern used

This utilizes the Graph, Depth-First Search, Topological Sort interview pattern. There are two popular ways to solve this:

1. DFS with Coloring: Use three states (0: unvisited, 1: visiting, 2: safe). If you encounter a node that is currently being visited (state 1), you've found a cycle.
2. Kahn's Algorithm (Reverse BFS): Reverse all edges in the graph. Nodes with no outgoing edges in the original graph now have an in-degree of 0. Perform a topological sort; any node that can be processed is safe.

Example explanation

Imagine a graph: 0 -> 1, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> terminal.

• Nodes 0, 1, and 2 form a cycle.
• From node 0, one path is 0 -> 1 -> 2 -> 0... which never ends. So 0 is not safe.
• Node 3 is safe because its only path leads to a terminal node.
• The result would be [3].

Common mistakes candidates make

• Confusing Safety with Connectivity: Thinking a node is safe just because it can reach a terminal node. Remember, all paths must lead to a terminal node.
• Naive DFS: Using a simple boolean visited array that doesn't distinguish between "currently in recursion stack" and "already processed," which leads to incorrect cycle detection.
• Ignoring the Ascending Order: Forgetting to sort the resulting indices before returning.

Interview preparation tip

Master the "Three-Color DFS" technique. It is the gold standard for cycle detection in directed graphs. Assigning states like WHITE, GRAY, and BLACK allows you to efficiently prune searches and identify cyclic dependencies in linear time.