Jump Game - I
EasyTrack the furthest index you can reach
Problem
Given an array where each value is the max jump length from that index, return true if you can reach the last index starting from index 0.
Track the farthest index you can reach; if you ever stand beyond it, you're stuck.
The idea
Sweep left to right maintaining the furthest reachable index. If you ever stand on an index beyond that reach, you are stuck; otherwise reaching the end is guaranteed.
The trick
- Fail the moment `i > furthest`.
- Update furthest to max(furthest, i + nums[i]) at each step.
- O(n) time, O(1) space.
Step 1 of 4. Sweep left to right tracking the farthest index reachable so far. Values: 2, 3, 1, 1, 4. reach 0.
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.