Jump Game
mediumNeetCode 150greedyarraysdynamic-programming
Problem
Given a list where each value is the maximum forward jump from that position, decide whether you can reach the last index starting from the first.
Examples
Input: nums = [2, 3, 1, 1, 4]
Output: true
Jump 1 then 3 reaches the end.
Input: nums = [3, 2, 1, 0, 4]
Output: false
Position 3 is a dead end you cannot pass.
Constraints
- • 1 <= nums.length <= 10^4
- • 0 <= nums[i] <= 10^5
Hints(tap to reveal)
- 1. Track the furthest index reachable so far.
- 2. If you ever stand beyond it you are stuck.
Optimal approach(spoiler)
- Scan left to right tracking the furthest reachable index.
- If the current index exceeds that reach, the end is unreachable.
- Otherwise extend the reach using the current jump value.
- Succeed once the reach covers the last index.
- O(n) time, O(1) space.
Ready to solve it?
Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.
Practice in the editor