PPractick

The problem

A workflow engine models states as a directed graph. A state with no outgoing transitions is terminal. A state is safe if every possible path from it eventually reaches a terminal state, meaning no path can get trapped in a loop forever. Return all safe states in increasing order. Work backwards from the terminal states. Reverse every edge and run Kahn's algorithm on out-degrees: a node becomes safe once all of its outgoing edges lead to nodes already known to be safe.

Example: [[1,2], [2,3], [5], [0], [5], [], []] → [2, 4, 5, 6].

Function signature

vector<int> eventualSafeNodes(const vector<vector<int>>& graph);  // sorted ascending

Test cases

Input (adjacency list)	Output	Explanation
[[1,2],[2,3],[5],[0],[5],[],[]]	[2, 4, 5, 6]	0, 1, 3 can loop
[[1,2,3,4],[1,2],[3,4],[0,4],[]]	[4]	Everything else reaches a loop
[[1],[2],[]]	[0, 1, 2]	A chain to a terminal
[[0]]	[]	A self-loop is never safe
[[]]	[0]

(Confirm: the graph is directed and may contain self-loops; terminal nodes are safe.)

How interviewers phrase it

• "A node is safe if every possible path starting from it leads to a terminal node. Return all the safe nodes in ascending order" (LeetCode 802).

Clarifying questions to ask

1. Must every path be safe, or just one? (Every path.)
2. Are terminal nodes safe? (Yes.)
3. Self-loops? (Possible, and they make the node unsafe.)

Follow-ups to expect

1. "Why reverse the graph?"
2. "Why count out-degrees?"
3. "DFS alternative?"
4. "Which nodes are unsafe?"
5. "Complexity?"

Related questions

• Topo Sort Hard
• Course Schedule I Hard
• Shortest path in DAG Hard
• Detect a cycle in an undirected graph Hard
• Bipartite Graph (DFS) Hard
• Cycle Detection in Directed Graph (DFS) Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in