Problem overview
The method jump receives an array nums of non-negative integers. You start at index 0, and nums[i] is the longest jump you can make from index i. The method returns the minimum number of jumps needed to land on 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 to index 4. A single jump from index 0 can reach at most index 2, so one jump is not enough.
Approach: label each cell once, left to right
Let dp[k] be the minimum number of jumps needed to reach cell k. Cell 0 needs 0 jumps. The cells that cell 0 can reach in one jump need 1, the cells that only those cells can reach need 2, and so on.
A natural first attempt recomputes dp[k] for every cell by looking at every earlier cell that could jump to it. That works but costs O(n²). The faster idea is a single observation: dp values never decrease from left to right. If cell i is the first cell from which cell j can be reached, then no later cell can give j a smaller count, because later cells have dp values that are at least as large. So each cell needs its value assigned exactly once, by the first cell that reaches it.
A second pointer j remembers the first cell that has not been labelled yet. It only ever moves forward. For each cell i, the code labels every unlabelled cell up to i + nums[i] with dp[i] + 1 and pushes j past them. Because j never goes back, the inner loop does at most n steps in total across the whole run.
Here is the example. At the start dp = [0, 0, 0, 0, 0] and j = 1.
- At
i = 0,nums[0] = 2, so cells 1 and 2 getdp[0] + 1 = 1. Nowj = 3anddp = [0, 1, 1, 0, 0]. - At
i = 1,nums[1] = 3reaches up to index 4, so cells 3 and 4 getdp[1] + 1 = 2. Nowj = 5anddp = [0, 1, 1, 2, 2]. - The remaining values of
ihave nothing left to label, and the answer isdp[4] = 2.
Step by step
- Create
dpas aconstnumber[]withnew Array(nums.length).fill(0). Entry 0 really is 0, and every other entry is overwritten when its cell is first reached. - Declare
let j: number = 1. It marks the first cell no jump has reached yet; cell 0 is where we start. - Loop over every index
iofnums. - Add an inner
whileloop that continues whilejis reachable fromi(j <= nums[i] + i) and still inside the array (j < nums.length). - Label the cell. Write
dp[j++] = dp[i] + 1. The post-increment uses the oldjas the index and then adds 1, so one statement labels the cell and moves on. - Return
dp[nums.length - 1].
The solution in TypeScript
class Solution {
jump(nums: number[]): number {
const dp: number[] = new Array(nums.length).fill(0);
let j: number = 1;
for (let i = 0; i < nums.length; i++) {
while (j <= nums[i] + i && j < nums.length) {
dp[j++] = dp[i] + 1;
}
}
return dp[nums.length - 1];
}
}
TypeScript details worth knowing:
new Array(n).fill(0).new Array(n)makes an array withnempty slots, andfill(0)writes a 0 into each. The annotationnumber[]ondpis only for the compiler; at run time it is a plain array.- Post-increment as an index. In
dp[j++] = dp[i] + 1, the indexj++evaluates to the old value ofj, andjis increased afterwards. It is the same as writingdp[j] = dp[i] + 1; j++;on two lines. - Numbers, not integers.
numberis a floating-point type, but all values here are small whole numbers, so there is nothing to round or overflow.
Complexity
Time: O(n). The outer loop runs n times. The inner loop's pointer j only moves forward and stops at n, so the inner loop's body runs at most n - 1 times in total, not per value of i.
Space: O(n). The dp array has one entry per cell.
Edge cases and common mistakes
- One cell.
[0]returns 0. You already stand on the last index, and the inner loop never runs. - Jumps longer than needed.
[5, 1, 1]returns 1, since the boundj < nums.lengthkeeps the labelling inside the array. - Single steps.
[1, 1, 1, 1]returns 3, one jump per step. - Unreachable last cell. The method assumes the last index can be reached. For
[1, 0, 3], cell 1 is a dead end, yet cell 2 still gets labelled fromi = 2, itself, and the method returns 1, which is not a meaningful answer. The problem's inputs avoid this case. - Restarting
jfor everyi. Startingjati + 1each time would relabel cells and push the cost back towardsO(n²). It would also let later cells overwrite smaller values. - Dropping the bound
j < nums.length. A largenums[i]would write past the end ofdp. JavaScript arrays grow instead of throwing, so the array would silently get longer.
Testing
[2, 3, 1, 1, 4]gives2.[2, 3, 0, 1, 4]gives2.[1, 1, 1, 1]gives3.[5, 1, 1]gives1.[0]gives0.