Jump Game
Each cell is a maximum jump length; decide if the last index is reachable. Track the farthest index reachable so far — no DP needed.
- Category
- Greedy
- Time complexity
- O(n)
- Space complexity
- O(1)
Pseudocode
farthest ← 0 for each i ≤ farthest farthest ← max(farthest, i + a[i]) reachable if farthest ≥ last
Reference implementation
far = 0
for i, v in enumerate(a):
if i > far: return False
far = max(far, i + v)
return True