How do you approach Find Eventual Safe States?

Reverse the graph. Then terminal nodes (outdegree 0) become the sources, and safety propagates backwards.

What is the time complexity of Find Eventual Safe States?

Time complexity: O(V + E), plus O(V log V) for the final sort.. Space complexity: O(V + E).

What are common mistakes on Find Eventual Safe States?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

gitGood.dev

← Back to problems

Find Eventual Safe States

MediumAlgorithms

Description

You are given a directed graph as an adjacency list, where graph[i] lists the nodes reachable in one step from node i.

A node is terminal if it has no outgoing edges. A node is safe if every possible path starting from it leads to a terminal node - in other words, it can never get stuck in a cycle.

Return all safe nodes, sorted ascending.

Example 1

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

Example 2

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Output: [4]

Example 3

Input: graph = [[1],[0]]

Output: []

Constraints

- 1 <= graph.length <= 10^4 - 0 <= graph[i].length < graph.length - No duplicate edges - The graph may contain cycles and self-loops.

Find Eventual Safe States: approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

Reverse the graph. Then terminal nodes (outdegree 0) become the sources, and safety propagates backwards.
In the reversed graph, run Kahn's algorithm using each node's ORIGINAL outdegree as its indegree counter.
Every node the reverse topological sort manages to consume is safe. Anything left with a positive counter is on, or leads into, a cycle. Sort before returning.

The optimal approach

Show the approach: Reverse the edges and the definition becomes a topological sort

"Every path from here terminates" is awkward to check forwards - it quantifies over all paths. Reversing the graph turns it into something mechanical: a node is safe exactly when all of its successors are safe, and terminal nodes are safe by definition.

So build the reverse graph, and give each node a counter equal to its original outdegree (how many successors it is still waiting on). Terminal nodes start at 0 and seed the queue. Popping a safe node decrements the counter of each node that pointed at it; when a counter hits 0, all of that node's successors have been proven safe, so it is safe too.

This is Kahn's algorithm on the reversed graph, and the same property that gives cycle detection for free does the work here: any node inside a cycle, or with a path into one, never reaches counter 0 and is simply never emitted. Self-loops are handled without a special case - a node pointing at itself can never have its own counter drained.

The DFS three-colour alternative (white/grey/black) is equally valid and worth mentioning in an interview, but the reverse-Kahn version avoids recursion depth concerns at 10^4 nodes.

Time: O(V + E), plus O(V log V) for the final sort.
Space: O(V + E)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.