Intervals + Greedy
Greedy reach
Why it matters
Reachability checks appear in segmented downloads, level maps, and workflows where each position grants limited forward progress. Exploring every jump sequence or storing an answer for every destination does unnecessary work when only reachability matters. The decision must use one left-to-right pass and constant extra memory.
Example
Jump Game
From index i you may jump at most nums[i] steps forward. Return whether you can reach the last index.
- Input
- nums = [3, 2, 1, 0, 4]
- Output
- False
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Jump Game
nums = [3, 2, 1, 0, 4]→False
The baseline, Mark good positions from the end, is O(n²) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [3, 2, 1, 0, 4], the brute table checks many forward destinations from each index. Track one boundary instead: index 0 sets reach = 3, indexes 1 through 3 cannot extend it, and index 4 lies beyond it, so return False.
For [3, 2, 1, 0, 4], start with reach = 0. Index 0 is reachable and extends reach to 0 + 3 = 3. Index 1 can reach only 3, index 2 can also reach 3, and index 3 has jump 0, so the reachable range remains 0 through 3.
The loop next arrives at index 4, but 4 > reach. No earlier reachable index could jump across that gap, so return False. Taking the maximum at each visited index keeps the entire reachable prefix, not one chosen jump path.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.