#63

Jump Game

medium

arraydynamic-programminggreedy

You are given an integer array nums. You start at the first index, and each element nums[i] is the maximum number of steps you can jump forward from that position.

Return true if you can reach the last index, and false otherwise.

Example

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

Output: true

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

Constraints

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

Intuition

A first pass tracks every index that's reachable at all: mark index 0 reachable, then for every index already known to be reachable, mark each index its jump range can land on as reachable too.

function canJump(nums) {
  const n = nums.length;
  // reachable[i] tracks whether index i can be reached at all, starting from index 0.
  const reachable = new Array(n).fill(false);
  reachable[0] = true;
  for (let i = 0; i < n; i++) {
    if (!reachable[i]) continue; // nothing jumps from an index we can't even get to
    // Mark every index this position's jump range can land on.
    for (let step = 1; step <= nums[i] && i + step < n; step++) {
      reachable[i + step] = true;
    }
  }
  return reachable[n - 1];
}

Brute force — mark every index reachable from an already-reachable index: O(n²).

This is O(n²) — for a run of large jump values, the inner loop keeps re-marking indices that are already known to be reachable. Can we do better?

Notice we never actually need to know every reachable index — only the single farthest one. If the farthest reachable index so far already passes some index i, then i (and everything between the last frontier and it) is reachable too, without re-deriving it index by index. That's the Greedy farthest-reach idea: keep one running reach value and push it outward as you scan, instead of maintaining a whole table of reachable indices.

The stored solution folds the brute force's table down to that single variable: scan left to right, bail out the moment the current index is beyond reach (nothing earlier could have jumped this far), otherwise push reach out to i + nums[i].

Walking it through:

nums = [3, 0, 0, 1, 4] — reach = farthest index reachable so far

i↓

reach = max(0, 0+3) = 3

Index 0's value of 3 sends the frontier straight to index 3.

i↓

reach = max(3, 1+0) = 3

Index 1 is a zero — a dead end on its own — but the frontier already passed it, so it costs nothing.

i↓

reach = max(3, 2+0) = 3

A second zero at index 2 is just as harmless — the frontier reached past it two steps ago.

i↓

reach = max(3, 3+1) = 4

Index 3 finally extends the frontier again, reaching the last index.

i↓

reach = max(4, 4+4) = 8; scan ends

Index 4 — the last index — is within the frontier (4 ≤ 4), so it's reachable. The scan finishes without ever getting stuck: `true`.

nums = [2, 1, 0, 0, 4] — a case that gets stuck

i↓

reach = max(0, 0+2) = 2

Index 0 can jump up to 2 steps, pushing the frontier to index 2.

i↓

reach = max(2, 1+1) = 2

Index 1 only matches what the frontier already covers — no gain, but still safely reachable.

i↓

reach = max(2, 2+0) = 2

Index 2 sits right at the edge of the frontier (2 ≤ 2) — reachable, but its value of 0 can't push the frontier any further.

i↓

3 > reach (2) → return false

Index 3 lies just beyond the frontier — nothing earlier jumped far enough to reach it, so the scan stops here: `false`.

Optimization

Greedy farthest reach

Track the farthest index reachable so far. Scan left to right; if the current index is beyond that reach, you're stuck and the answer is false. Otherwise extend the reach to max(reach, i + nums[i]). If you finish the scan, the last index was reachable.

O(n) time, O(1) space.

function canJump(nums) {
  let reach = 0; // farthest index reachable so far
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false; // this index is unreachable — stuck for good
    reach = Math.max(reach, i + nums[i]); // extend the frontier as far as this jump allows
  }
  return true; // scanned every index without ever getting stuck
}

Complexity analysis

Time complexity: O(n). Here's why:

The scan visits each of the n indices exactly once.
At each index, comparing i against reach and updating reach with Math.max is O(1) work.

So the whole scan is a single pass — O(n) — instead of the brute force's O(n²) of re-marking already-known-reachable indices.

Space complexity: O(1). Here's why:

Only reach and the loop index i are kept, regardless of the input's length.
No table of reachable indices is built, unlike the brute force's O(n) reachable[] array.

So the greedy scan uses O(1) auxiliary space beyond the input itself.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [7]	true	Single element — already at the last index, regardless of its value.
nums = [0,5]	false	Smallest impossible case — index 0's value of 0 means you can never leave it.
nums = [2,2,2]	true	All-equal jump values — still reachable since the frontier compounds each step.
nums = [2,2,2,2,1]	true	Repeated jump values keep the frontier exactly one step ahead of the scan the whole way, clearing the last index just in time.
nums = [1,1,1,1,0]	true	Tight fit — the frontier lands exactly on the last index, whose own value of 0 doesn't matter.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor