Jump Game

The key idea

Track the farthest index reachable so far. Scan left to right; if you ever stand on an index that is beyond that farthest reach, you are stuck and can never move forward. If the reach ever covers the last index, the answer is true.

Problem

You are given an integer array nums. You start at the first index of the array, and each element nums[i] represents your maximum jump length at that position.

From index i, you can jump to any index from i + 1 up to i + nums[i] (as long as it stays inside the array). Return true if you can reach the last index, or false otherwise.

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

Examples

Input: nums = [2,3,1,1,4] Output: true

Input: nums = [3,2,1,0,4] Output: false

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →