Find Eventual Safe States

Medium#802from the dead ends back

You get a directed graph: for each node, the list of nodes it has arrows to. A node with no arrows out is a dead end. A node is safe if every walk from it, whichever arrows it follows, ends at a dead end. Return all safe nodes in increasing order. Our example: 0 → [1, 3], 1 → [2, 5], 2 → [], 3 → [4], 4 → [6], 5 → [], 6 → [3, 5]. The answer is [1, 2, 5].

802 Find Eventual Safe StatesWalkthrough · 1×

Example: 7 nodes. The number above a node is its out-degree: its exits not yet known to lead somewhere safe. The run walks the arrows backwards, from the dead ends.

0123456queuefront on the left—safe—
has exits not known safein the queuecurrent nodewhere the reversed arrow leadssafenever safe: a walk from it can loop

Reverse every arrow to know who leads into each node: 1 ← 0; 2 ← 1; 3 ← 0, 6; 4 ← 3; 5 ← 1, 6; 6 ← 4

01/25
restart · back · play · step
Speed
1function eventualSafeNodes(graph):
2 back = every arrow of graph reversed
3 outdegree = arrows out of each node
4 queue = nodes with outdegree 0
5 safe = []
6 while queue is not empty:
7 node = queue.popFront()
8 safe.pushBack(node)
9 for prev in back[node]:
10 decrease outdegree[prev] by 1
11 if outdegree[prev] is 0:
12 queue.pushBack(prev)
13 return sorted(safe)
state
outdegree
–
queue
–
safe
–
node
–
prev
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A dead end is safe. A node is safe exactly when all its arrows lead to safe nodes, so it joins the queue once its count of exits not known safe reaches 0.
  2. A node on a loop always keeps the arrow that goes on round the loop, and so does a node with an arrow into a loop: their count never reaches 0.
  3. The card counts arrows in and starts from what waits for nothing; here the arrows are walked backwards, so the count is of arrows out and the start is the dead ends.

Complexity

Time O(n + e + n log n) for n nodes and e arrows: each arrow is reversed and walked back once, each node enters the queue at most once, and the safe nodes are sorted at the end. Memory O(n + e) for the reversed arrows, the counts and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.