States That Always Halt
MediumGraphs
Problem
A state machine has n states numbered 0 to n - 1. Each entry [u, v] of transitions lets the machine move from state u to state v. A state with no outgoing transition halts the machine.
A state is safe if, no matter which transitions are taken from it, the machine always reaches a halting state; equivalently, no path from it can run forever. Return all safe states in ascending order.
Example 1
- Input:
- n = 6, transitions = [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [1, 3]]
- Output:
- [3, 4, 5]
0 → 1 → 2 → 0 can loop forever, so 0, 1 and 2 are unsafe even though 1 can also move to 3. From 3, 4 or 5 every path ends at 5.
Example 2
- Input:
- n = 4, transitions = []
- Output:
- [0, 1, 2, 3]
Every state halts immediately.
Example 3
- Input:
- n = 3, transitions = [[0, 0], [1, 0], [2, 1]]
- Output:
- []
State 0 loops on itself and everything leads to it.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ transitions.length ≤ 5·10^4
- 0 ≤ u, v < n
Hint
Show the first hint
Halting states are safe. When can you be sure another state is safe?
Walkthrough
How to approach it
01Clarify before coding
- Is one bad option enough to make a state unsafe? Yes: safe means every path halts.
- Do self-transitions count as loops? Yes, a state that can move to itself can run forever.
- Can transitions repeat? Yes; count each copy in the out-degree and remove each copy once.
02Brute force
For each state, run a DFS that explores every path and looks for a cycle reachable from it.
Cost: O(n · (n + m)) without sharing results: 6·10^8 steps for a long chain.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.