Problem overview
The function jump receives a vector nums of non-negative integers. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any distance from 1 up to nums[i] is allowed. The function returns the minimum number of jumps that gets you to the last index. The lesson's tests use arrays where the last index can be reached.
For nums = [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 from index 0 reaches index 4, because nums[0] is only 2.
Approach: minimum jumps per cell, filled in order
Let dp[k] be the minimum number of jumps needed to reach cell k from cell 0. Then dp[0] is 0, and the answer is dp[n - 1]. A cell i reaches every cell from i + 1 up to i + nums[i] with one more jump than dp[i] took.
A direct version would loop over each cell i and every cell it reaches and keep the smaller value, which can take O(n²) time. A property of this problem makes that unnecessary: dp never decreases from left to right. To see why, take the shortest route to cell j + 1 and look at the cell p it jumps from. If p is before j, that same jump also lands on j, so dp[j] <= dp[j + 1]. If p is j itself, dp[j + 1] is dp[j] + 1.
The consequence is that the first cell i (scanning from the left) that can reach a cell j gives j its best value, dp[i] + 1. Any later cell has a dp value that is at least as large. So each cell receives its value once and never needs an update.
A single pointer j, the first cell that no jump has reached yet, is enough to track which cells still need a value. For each i, the pointer moves forward over every cell that i reaches and has not been reached before.
On [2, 3, 1, 1, 4], the table starts as [0, 0, 0, 0, 0] with j = 1:
- At
i = 0, the reach is0 + 2 = 2, so cells 1 and 2 getdp[0] + 1 = 1, andjbecomes 3. - At
i = 1, the reach is1 + 3 = 4, so cells 3 and 4 getdp[1] + 1 = 2, andjbecomes 5. - For the remaining
i,j < nis false, so nothing changes.
The final table is [0, 1, 1, 2, 2], and dp[4] is 2.
Step by step
- Store the length in
nand createdpas a vector ofnzeros. Entry 0 is correct as it is, and every other entry is overwritten when its cell is first reached. - Create the pointer
jas ausizestarting at 1: cell 0 is the start, so the first cell without a value is cell 1. - Loop over every cell
ifrom left to right. - Add a
whileloop that runs whilejis within the reach ofiand still inside the vector. - Assign and advance. Cell
jis reached for the first time, so its value isdp[i] + 1. Thenjmoves on to the next cell. - Return
dp[n - 1]as the final expression.
The solution in Rust
impl Solution {
fn jump(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut dp = vec![0i32; n];
let mut j = 1usize;
for i in 0..n {
while j <= (nums[i] + i as i32) as usize && j < n {
dp[j] = dp[i] + 1;
j += 1;
}
}
dp[n - 1]
}
}
Rust details worth a closer look:
- Casting for the comparison.
nums[i]is ani32whileiandjareusize. The expressionnums[i] + i as i32castsifirst, becauseasbinds tighter than+, and adds the two asi32. The sum is cast back tousizeto compare withj. Since the values are non-negative, the cast keeps the number unchanged. - Type suffixes.
vec![0i32; n]and1usizepin the types of the literals, so no type annotation is needed. - No
++. Rust has no increment operator, so the code writesj += 1;. - The final expression.
dp[n - 1]has no semicolon, so it is returned. For an empty vector,n - 1on ausizewraps in an optimized build (and panics in a debug build), and the index is then out of bounds, so the program panics either way. The lesson's inputs are never empty.
Complexity
Time: O(n). The outer loop runs n times. The pointer j only moves forward and stops at n, so the inner while loop runs at most n times across the whole function, not per cell.
Space: O(n). The dp vector holds one integer per cell.
Edge cases and common mistakes
- A single element. For
[0]you are already on the last index. Thewhilecondition fails immediately becausej = 1is not less thann = 1, and the function returnsdp[0], which is 0. - A first jump that covers everything.
[5, 0, 0, 0, 0, 0]returns 1. Cells beyond the end are never touched, thanks to thej < ncheck. - Ones everywhere.
[1, 1, 1, 1]returns 3, one jump per step. - Forgetting
j < n. A cell can reach farther than the end of the vector. Without the bound,dp[j]would be written past the end, which panics. - Revisiting cells. Each cell must receive its value once. If a later
ioverwrote a cell that already has one, it would replace a smaller value with a larger or equal one, so the pointerjmust only move forward. - Unreachable end. The method assumes the last index can be reached. For
[3, 2, 1, 0, 4]it returns 1, which means nothing here, because no jump sequence gets past the 0. Check reachability separately if your inputs allow it.
Testing
[2, 3, 1, 1, 4]gives 2.[0]gives 0.[1, 1, 1, 1]gives 3.[2, 1]gives 1.[1, 2, 3]gives 2.
