Jump Game II

GREEDY · MEDIUM

The problem

You start at index 0 of an array nums. From index i, you can jump forward to any index up to (and including) i + nums[i] — nums[i] is the maximum jump length from that position, not a fixed one. Return the minimum number of jumps needed to reach the last index. The input is always guaranteed solvable — the last index is always reachable.

Solution 1: Brute force — DP over every earlier index

Let dp[i] be the minimum jumps needed to reach index i. To fill in dp[i], look at every earlier index j < i: if j can reach i (i.e. j + nums[j] >= i), then dp[i] could be dp[j] + 1. Take the best such j. This is correct but checks every (i, j) pair, even though most of those earlier indices were never going to be part of an optimal path.

Interactive visualization

nums = [2, 3, 1, 1, 4, 2] — DP brute force checking every earlier index for each position

Press Play or Step to begin.

Step 0 / 22

The code

function jumpBruteForce(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (j + nums[j] >= i && dp[j] + 1 < dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  return dp[n - 1];
}

Line by line:

dp[i] starts at Infinity — “not yet reachable” — except dp[0] = 0, the base case: standing at the start costs zero jumps.
j + nums[j] >= i asks “can a jump from j land on or past i?” — this is checked fresh for every single (i, j) pair, with no memory carried over from the previous i.
dp[j] + 1 < dp[i] only updates when this particular j produces a strictly better answer than anything found so far for this i.
The double loop is the whole story: n outer iterations, each scanning up to n earlier indices — O(n²) total.

Complexity

Time	Space	Approach
O(n²)	O(n)	DP re-scanning every earlier index for every i

Solution 2: Optimal — greedy one-pass, track the reachable boundary

Instead of asking “what’s the best index to jump from,” track two boundaries as you scan once, left to right: currentEnd — the farthest index reachable with the jumps taken so far — and farthest — the farthest index reachable from any index seen so far, even ones inside the current jump’s range. Every index in between gets scanned exactly once to update farthest. The moment i reaches currentEnd, that jump’s range is exhausted — take another jump and set currentEnd to the best boundary found (farthest). No index is ever revisited.

Interactive visualization

nums = [2, 3, 1, 1, 4, 2] — Same example as above, same answer: 3 jumps, one pass

Press Play or Step to begin.

Step 0 / 10

The code

function jumpOptimal(nums) {
  const n = nums.length;
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < n - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Line by line:

The loop stops at n - 1, not n — once i reaches the last index, no further jump is ever needed, so there is nothing left to check.
farthest = Math.max(farthest, i + nums[i]) runs on every iteration, whether or not a jump is taken this step — it’s the running memory of “the best boundary found in this window so far,” and it would be wrong to only update it right before a jump.
i === currentEnd is the trigger, not i >= currentEnd or i > currentEnd — the loop passes through currentEnd exactly once, so exact equality is both sufficient and clearer about intent.
currentEnd = farthest commits to the best boundary discovered across the whole window just finished — this is the greedy choice, made once per jump, never revisited.

Complexity

Time	Space	Approach
O(n)	O(1)	Single pass tracking two boundary variables

Complexity comparison

Solution	Time	Space
Brute force (DP, re-scan every j)	O(n²)	O(n)
Optimal (greedy one-pass)	O(n)	O(1)

This is a genuine asymptotic improvement in both dimensions, not just a constant-factor speedup — the greedy solution drops from quadratic to linear time by proving that the quadratic DP’s “check every earlier j” work can be replaced with two running variables, and drops from O(n) space to O(1) since no dp array needs to be stored at all.

Interview corner

Why is it safe for the greedy solution to never reconsider an earlier choice, once currentEnd has advanced?

Minimum jump count only depends on which range of indices is reachable after each jump — not on which specific index within that range you “chose” to jump from.
farthest already captures the best possible next boundary achievable from anywhere in the current window, by the time currentEnd is reached.
Any alternative strategy that reaches a smaller boundary using the same jump count can never beat this one — it only limits future options, never helps them.

Why doesn’t the greedy version track which index to jump to, only the reachable boundary?

The problem only asks for the minimum count of jumps — not the actual path.
Jump count is fully determined by how many times the boundary has to advance to cover the array, which needs only two running numbers (currentEnd, farthest).
If the actual sequence of indices were required, you’d additionally record, for each jump, which index produced the new farthest — a small addition, not a different algorithm.

What guarantees farthest is always beyond currentEnd whenever another jump is actually needed?

The problem guarantees the last index is always reachable — there’s always some index in the current window whose reach extends past currentEnd (until currentEnd already covers the last index).
Without that guarantee, farthest could stall at currentEnd forever — this greedy loop relies on solvability being promised, it doesn’t verify it.

Trick question — what does this log?

const nums = [1, 0, 2, 0, 3];
let reachable = 0;
for (let i = 0; i < nums.length; i++) {
  if (nums[i]) reachable++;
}
console.log(reachable);

Answer: 3, not 5.
if (nums[i]) treats 0 as falsy and silently skips it — but in this problem, a jump length of 0 is a real, meaningful value (it means “stuck here,” not “no value present”).
The two indices holding 0 never increment reachable, even though they’re perfectly valid array entries.
⚠ Trap: this is exactly why the verified solutions above always compare with >=/Math.max against real numeric values, never a bare truthiness check on nums[i] — a 0 jump length must be read as the number zero, never treated like a missing or false value.

Quiz

1. Why does the greedy solution only increment jumps when i === currentEnd, not on every iteration?

Every index requires its own jump, so it increments every iteration
currentEnd marks the last index covered by jumps taken so far — reaching it means that jump’s whole range is used up and another jump is now required
It’s an arbitrary implementation choice with no effect on correctness

2. Why must farthest = Math.max(farthest, i + nums[i]) run on every loop iteration, not just on iterations where a jump is taken?

farthest has to capture the best reach across the WHOLE current window — any index in that window, not just the last one, might give the longest reach
It’s purely a performance optimization with no effect on the answer
farthest only matters at the exact moment a jump is taken

3. Why does the brute-force DP need to check every earlier index j for each i, while the greedy solution never re-examines a past index?

Greedy proves that all useful information from earlier indices can be summarized in one running “farthest reachable” value, eliminating the need to re-check them
They solve different problems, so the comparison doesn’t apply
The DP version is simply wrong and doesn’t need to check every j

4. What’s the core argument for why always advancing to farthest (the maximum reach found) is optimal, not just “usually good”?

For the same number of jumps taken, landing on the farthest possible boundary can never leave you in a worse position than any other valid choice — only ever the same or better
It happens to work on the LeetCode examples but has no general proof
Because it minimizes the length of each individual jump

5. What’s the time complexity of each solution, and what causes the difference?

Brute force O(n²) from re-scanning every earlier j for each i; optimal O(n) from a single pass with two running variables
Both are O(n) — the greedy version is just a cleaner rewrite with the same complexity
Brute force is O(n); optimal is O(n²)