Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Preserve the best reachable frontier: The Furthest Step.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Greedy reachability matches the clues
- 2Keep this true after every move: furthest is the maximum reachable index from the processed prefix
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: furthest is the maximum reachable index from the processed prefix
Lesson 1 of 3
Live algorithm trace
Greedy reachability
Complete execution1 of 6
Only index 0 is known reachable before the scan begins.
1
furthest = 02
if i > furthest: return false3
furthest = max(furthest, i + nums[i])4
return truefurthest = 0
Truth to preserve / Cost target
Truth to preserve
furthest is the maximum reachable index from the processed prefix
Cost target
O(n)
A greedy scan keeps the furthest reachable index. Every position at or before that frontier is usable, and each jump may extend the frontier.
Your call · What should guide every step of this algorithm?