802. Find Eventual Safe States
Asked at Uber
Difficulty
Medium
Time
O(n + e)
Space
O(n + e)
Pattern
Depth-First Search
Companies
1
Problem
You are given a directed graph with n nodes, labeled 0 to n-1. It is given as graph, where graph[i] is the list of nodes that node i has an edge to. A node with an empty list has no outgoing edges; we call it a terminal node.
A node is safe if every path that starts at that node eventually reaches a terminal node. In other words, no matter which edges you follow, you can never get stuck in a loop forever. A node that can reach a cycle is not safe.
Return all safe nodes, sorted in ascending order.
Safe vs unsafe nodes
Constraints
- ●
n == graph.length - ●
1 <= n <= 10^4 - ●
0 <= graph[i].length <= n - ●
0 <= graph[i][j] <= n - 1 - ●
graph[i] is sorted in strictly increasing order - ●
The graph may contain self-loops - ●
The number of edges is in the range [1, 4 * 10^4]
Examples
graph = [[1,2],[2,3],[5],[0],[5],[],[]][2,4,5,6]graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]][4]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
How to Think About It
Brute force: From each node, DFS to check if all paths lead to terminal nodes — O(n*(n+e)) time.
Memoization: Mark nodes as safe/unsafe/cycling to avoid recomputation — O(n+e) time.
Graph coloring: 0=unvisited, 1=visiting, 2=safe. A node is safe if all children are safe.
Topological sort (Kahn's): Reverse the graph and use BFS from terminal nodes, peeling in-degree layer by layer.
Optimal: DFS with three-state coloring or reversed-graph BFS — both O(n+e) time and O(n+e) space.
Optimal Approach
Reverse the graph and compute in-degrees. Start BFS from all nodes with in-degree 0 (terminal nodes in the original graph). Process nodes in topological order: for each dequeued node, decrement in-degrees of its predecessors in the reversed graph. Nodes that reach in-degree 0 are safe. This is essentially Kahn's algorithm on the reversed graph, running in O(n+e) time and space.
Peel terminal nodes backwards
What Trips People Up in Real Interviews
Clarify: only terminal nodes (no outgoing edges) are initially safe.
Think about cycles: any node that can reach a cycle is unsafe.
Reverse the graph and BFS from nodes with no incoming edges to find safe states efficiently.
Label nodes as you process them: unvisited, visiting (in current DFS path), processed.
Return the answer sorted — the problem guarantees a sorted output.
Solution Code
O(n + e) timefrom collections import deque
class Solution:
def eventualSafeNodes(self, graph):
n = len(graph)
rev = [[] for _ in range(n)]
indeg = [0] * n
for u in range(n):
for v in graph[u]:
rev[v].append(u)
indeg[u] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
node = q.popleft()
for prev in rev[node]:
indeg[prev] -= 1
if indeg[prev] == 0:
q.append(prev)
return sorted(i for i in range(n) if indeg[i] == 0)Frequently Asked Questions
What is the Find Eventual Safe States problem?
Given a directed graph with n nodes (0 to n-1) where graph[i] lists all nodes node i points to, find all eventual safe states. A node is eventually safe if all paths starting from it eventually reach a terminal node (a node with no outgoing edges). Return the sorted list of safe node indices.
How do you solve Find Eventual Safe States?
The optimal approach runs in O(n + e) time and O(n + e) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find Eventual Safe States?
Find Eventual Safe States is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Find Eventual Safe States?
- Clarify: only terminal nodes (no outgoing edges) are initially safe.
- Think about cycles: any node that can reach a cycle is unsafe.
- Reverse the graph and BFS from nodes with no incoming edges to find safe states efficiently.
- Label nodes as you process them: unvisited, visiting (in current DFS path), processed.
- Return the answer sorted — the problem guarantees a sorted output.