medium

Jump Game

Check whether you can reach the last position of an array given each element's max jump length.

1. Define the problem

Jump Game

You are given an integer array nums. You start at index 0, and each numsi is the maximum number of steps you can jump forward from index i. Return true if you can reach the last index, or false otherwise. Use a greedy single pass: track the farthest reachable index seen so far. If you ever reach an index beyond that farthest point, you're stuck and can stop early.

Constraints

  • 1 ≤ nums.length ≤ 104
  • 0 ≤ numsi ≤ 105

Example

Inputnums = [2, 3, 1, 1, 4]
Outputtrue

Explanation Jump 1 step from index 0 to index 1, then 3 steps to the last index.

2. Visualize the solution

Track the farthest reachable index in one pass

Track the farthest reachable index in one pass
Statusfarthest=0→2

i=0: nums[0]=2, so the farthest reachable index becomes 0+2=2.

What happens in this step

i = 0, farthest = 0
nums[0] = 2
farthest = max(0, 0 + 2) = 2

i (0) is not beyond farthest (0), so we're not stuck yet. farthest updates to 2, meaning index 2 is now reachable.
Step 1 of 3

Steps to visualize

  1. Track the farthest index reachable so far, starting at 0.
  2. At each index i, if i is beyond the farthest reachable point, you are stuck — return false.
  3. Otherwise update farthest to max(farthest, i + numsi).
  4. If farthest ever reaches or passes the last index, return true immediately.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track the farthest reachable index in one pass
Statusfarthest=0→2

i=0: nums[0]=2, so the farthest reachable index becomes 0+2=2.

What happens in this step

i = 0, farthest = 0
nums[0] = 2
farthest = max(0, 0 + 2) = 2

i (0) is not beyond farthest (0), so we're not stuck yet. farthest updates to 2, meaning index 2 is now reachable.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function canJump(nums) {
  let farthest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
    if (farthest >= nums.length - 1) return true;
  }

  return true;
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [2, 3, 1, 1, 4]trueexample from the docstring
nums = [3, 2, 1, 0, 4]falsegets stuck at the guaranteed zero before reaching the end
nums = [1, 0, 0, 0]falsereaches index 1 but can move no further
nums = [5, 0, 0, 0, 0]truea single jump from the start already covers the whole array
nums = [0]truesmallest valid input, already at the last index
nums = [1, 0]trueboundary case, one jump reaches the last index
nums = [0, 1]falsestuck at index 0 with no way to move

Keep reading