Jump Game
MediumTrack the farthest reachable index
Track the farthest spot you can reach; if you can always reach at least the next spot, you can finish.
The idea
Sweep left to right keeping the farthest index you can reach. If you ever stand on an index beyond that reach, you're stuck; if reach covers the last index, you win.
2
3
1
1
4
0
1
2
3
4
reach0
Step 1 of 4. Sweep left to right tracking the farthest index reachable so far. Values: 2, 3, 1, 1, 4. reach 0.
1/4
Optimal
timeO(n)spaceO(1)
One number to maintain.
1let reach = 0;2for (let i = 0; i < n; i++) {3 if (i > reach) return false;4 reach = Math.max(reach, i + nums[i]);5}6return true;Input
- array
- [2, 3, 1, 1, 4]
Memory
- i
- —
- reach
- 0
Output
- reach
- 0
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 3, 1, 1, 4]
- Output:
- true
- Explanation:
- You can hop to the last index.
Example 2
- Input:
- nums = [3, 2, 1, 0, 4]
- Output:
- false
- Explanation:
- The 0 traps you before the end → false.
Example 3
- Input:
- nums = [0]
- Output:
- true
- Explanation:
- You're already at the end.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.