Problem overview
You stand on index 0 of an array of non-negative integers. The number at each index is the longest jump you can make from there: a value of 3 lets you move forward by 1, 2 or 3 positions. The method jump(nums) returns the minimum number of jumps needed to reach the last index.
For [2, 3, 1, 1, 4] the answer is 2. Jump 1 step from index 0 to index 1, then 3 steps from index 1 to the last index. No single jump works, because the 2 at index 0 only reaches index 2.
The lesson asks for an iterative solution in O(n²) time and O(n) extra space. It is the bottom-up version of a memoized recursion: the same table of subproblem answers, filled in a loop instead of by recursive calls.
Approach: minimum jumps from every index to the end
Define dp[i] as the minimum number of jumps needed to get from index i to the last index. The answer is dp[0].
The recurrence comes from looking at the first jump. From index i you can land on any index j from i + 1 to i + nums[i], as long as j is inside the array. That jump costs 1, and then you need dp[j] more. So:
dp[last] = 0
dp[i] = 1 + min(dp[j]) for j from i + 1 to min(i + nums[i], last)
Every dp[i] depends only on entries to its right. Filling the table from right to left therefore guarantees that each entry we read is already final. This is what removes the recursion: no call stack, no repeated work, and no risk of a stack overflow on a long array.
Two other approaches exist for this problem. Plain recursion tries every jump from every index and repeats the same subproblems, which takes exponential time without memoization. A greedy scan that tracks the farthest reachable index runs in O(n) time. This lesson sticks to the table because it shows how dynamic programming works and generalizes to variants of the problem, such as jumps with costs.
Step by step
- Create
dp. It hasnums.lengthslots, all set tonums.length. That number acts as infinity: the true answer is at mostn - 1jumps (one per step), so no real answer can equaln, andMath.minwill overwrite it as soon as a real path is found.new Array(n)alone creates empty slots, so.fill(...)is needed; it returns the array, which allows the chaining. - Set the last cell to 0. Standing on the last index needs no jumps. This is the base case that all other entries are built on.
- Loop
ifromnums.length - 2down to 0. The last cell is already done, so the loop starts one before it and moves left. - Loop
jover the cells reachable in one jump. It starts ati + 1and runs whilej < nums.lengthandj <= i + nums[i]. The first test keepsjinside the array when the jump is longer than the remaining distance. - Take the smaller value.
dp[i] = Math.min(dp[i], 1 + dp[j])keeps the best first jump seen so far. - Return
dp[0]. After both loops every entry is final.
The solution in JavaScript
class Solution {
jump(nums) {
let dp = new Array(nums.length).fill(nums.length);
dp[nums.length - 1] = 0;
for (let i = nums.length - 2; i >= 0; --i) {
for (let j = i + 1; j < nums.length && j <= i + nums[i]; ++j) {
dp[i] = Math.min(dp[i], 1 + dp[j]);
}
}
return dp[0];
}
}
The table for [2, 3, 1, 1, 4] starts as [5, 5, 5, 5, 0] and changes like this as i moves left:
i | Reachable j | dp afterwards |
|---|---|---|
| 3 | 4 | [5, 5, 5, 1, 0] |
| 2 | 3 | [5, 5, 2, 1, 0] |
| 1 | 2, 3, 4 | [5, 1, 2, 1, 0] |
| 0 | 1, 2 | [2, 1, 2, 1, 0] |
At i = 1 the value 3 reaches the last index directly, so dp[1] is 1. At i = 0 the best choice is to land on index 1, giving 1 + dp[1] = 2. Landing on index 2 would cost 1 + dp[2] = 3.
JavaScript details
new Array(n)versusfill.new Array(3)is an array of three empty slots, not three zeros.new Array(3).fill(9)gives[9, 9, 9].--iand++j. In a loop header,i--and--ibehave the same, because the value of the expression is not used.Math.mintakes any number of arguments and returns the smallest. With the sentinelnums.lengthindp[i], the first real candidate always wins.
Complexity
- Time:
O(n²). The outer loop runs about n times, and the inner loop can run up to n - i times. When every value is large, such as[n, n, n, ...], the total is close to n²/2 steps. - Space:
O(n). Thedparray has one entry per index. There is no recursion, so nothing else grows with the input.
Edge cases and common mistakes
- A single element.
[0]returns 0:dp[0]is the last cell, set to 0, and the loop does not run. - Zeros. A 0 at index
imeans no jumps from there, the inner loop does not run, anddp[i]keeps the sentinel. Because of that, a later1 + dp[i]never beats a real path. - Unreachable end. For
[1, 0, 5]the last index cannot be reached, and the method returns 3, the sentinel, which is not a jump count. The problem gives inputs where the end is reachable. If you need to handle the other case, compare the result withnums.length. - Going left to right. Filling
dpfrom the start would read entries that are not final yet. The right-to-left order is what makes the recurrence valid. - Running past the array. Without the
j < nums.lengthtest, a largenums[i]makesjpoint atundefined, and1 + undefinedisNaN. - Always taking the longest jump. In
[2, 3, 1, 1, 4], jumping 2 from index 0 lands on a 1 and costs three jumps in total. The best first jump is the shorter one. The table tries every option instead of guessing.
Testing
[2, 3, 1, 1, 4]gives 2.[0]gives 0.[1, 1, 1, 1]gives 3, one jump per step.[5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0]gives 3.
