What is the brute force approach and complexity for Find Eventual Safe States?

For each node, search everything it can reach and check whether the search runs into a loop with time complexity O(V · (V + E)) and space complexity O(V).

What is the optimal approach and complexity for Find Eventual Safe States?

Count arrows out; start from terminal nodes; a node joins once all of its arrows lead to safe nodes with optimal time complexity O(V + E) and space complexity O(V + E).

How do you identify the pattern for Find Eventual Safe States?

Look for key signals in the prompt: "safe node" indicates Every walk from it must end. That is stronger than 'not on a loop': a node that only leads into a loop is unsafe too.; "every possible path" indicates We must rule out loops reachable from the node, not only loops that pass through it.; "sorted in ascending order" indicates Read the node labels in index order at the end, so the output comes out sorted for free..

Find Eventual Safe States

Medium·LeetCode #802 Pro OnlySlight Variation

LeetCode

Problem Statement

There are n nodes labelled from 0 to n − 1. graph[i] lists the nodes that node i has an arrow to.

A node is terminal if it has no arrows going out. A node is safe if every walk that starts there ends at a terminal node or at another safe node. In other words, no walk from a safe node can go round a loop forever.

Return all the safe nodes, sorted in ascending order.

Input

graph, an adjacency list: graph[i] is the list of nodes that i points to.

Output

The safe nodes, sorted in ascending order.

Example 1

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

Output: [2,4,5,6]

Nodes 5 and 6 have no arrows out, so they are terminal. Nodes 2 and 4 only point at 5, so they are safe. Nodes 0, 1 and 3 form the loop 0 → 1 → 3 → 0, so a walk from any of them can go round forever.

Example 2

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

Output: [4]

Only node 4 is terminal. Node 1 has an arrow to itself, and nodes 0, 2 and 3 can reach the loop 0 → 3 → 0, so none of them is safe.

Constraints

• 1 ≤ n ≤ 10^4
• 0 ≤ graph[i].length ≤ n
• 0 ≤ graph[i][j] ≤ n − 1
• Each graph[i] is sorted in strictly increasing order.
• The graph may contain self-loops.
• The number of arrows is between 1 and 4 · 10^4.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“safe node”

→ Every walk from it must end. That is stronger than 'not on a loop': a node that only leads into a loop is unsafe too.

“every possible path”

→ We must rule out loops reachable from the node, not only loops that pass through it.

“sorted in ascending order”

→ Read the node labels in index order at the end, so the output comes out sorted for free.

Approach Complexity Ladder

Brute Force — search from each node for a loopO(V · (V + E))O(V)

For each node, search everything it can reach and check whether the search runs into a loop

Optimal — reverse the arrows and peel from the terminal nodesO(V + E)O(V + E)

Count arrows out; start from terminal nodes; a node joins once all of its arrows lead to safe nodes

Brute Force Intuition

A node is unsafe exactly when a loop can be reached from it. For each node, run a search that follows arrows and keeps track of the nodes on the current path. If the search steps onto a node that is already on the path, a loop is reachable and the node is unsafe.

Recognition rule for this sub-pattern:

If Kahn processes fewer than n nodes (or DFS finds a "visiting" node again), there is a cycle.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Detect Cycle in a Directed Graph