Problem overview
The function jump receives a vector of non-negative integers, nums. You start at index 0, and nums[i] is the longest jump you can make from index i: any distance from 1 up to nums[i]. The function returns the smallest number of jumps needed to reach the last index.
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, which is index 4. Reaching index 4 in a single jump is impossible, because nums[0] is only 2.
Approach: try every first jump, ask the same question again
This lesson is in the backtracking chapter, so it starts with the most direct idea. Define min_jumps(nums, i) as the fewest jumps needed to reach the last cell starting from cell i. The answer to the problem is min_jumps(nums, 0).
- If
iis the last index, no more jumps are needed: the answer is 0. - Otherwise, a jump can land on any cell
jfromi + 1toi + nums[i](not past the end). After landing onjthe problem is the same one, starting fromj. So the cost of that choice is1 + min_jumps(nums, j), and the answer foriis the smallest cost over all choices.
Every recursive call moves to a larger index, so the calls always end at the last cell. The helper explores every route and keeps the best, which is why this is called backtracking: each choice is tried, its result is recorded, and the search goes back to try the next one.
For the example, from index 0 the choices are indexes 1 and 2. From index 1 the choices are 2, 3 and 4, and index 4 is the goal, so min_jumps(nums, 1) is 1. From index 2 the only choice is index 3, then index 4, which is 2 jumps. The best first jump is therefore to index 1, for a total of 1 + 1 = 2.
Step by step
- Call the helper from
jump. The body isSolution::min_jumps(&nums, 0)as the final expression, with no semicolon. The&lends the vector to the helper. - Declare the helper above
jump. It borrowsnumsas&Vec<i32>, takes the indexias ausize, and returns ani32. - Base case. When
iequalsnums.len() - 1, return 0. - Start
resultat a large value. It is set tonums.len() as i32. No real path needs that many jumps, since the most it can take isnums.len() - 1, so any real path replaces it. - Find the farthest reachable index,
max_j: the smaller ofi + nums[i]and the last index. The sum is computed ini32and the result converted back tousize. - Try every landing cell. A loop over
(i + 1)..=max_jupdatesresultwith the smaller of its value and1 + Solution::min_jumps(nums, j). - Return
resultas the final expression.
The solution in Rust
impl Solution {
fn min_jumps(nums: &Vec<i32>, i: usize) -> i32 {
if i == nums.len() - 1 {
return 0;
}
let mut result = nums.len() as i32;
let max_j = ((i as i32 + nums[i]).min(nums.len() as i32 - 1)) as usize;
for j in (i + 1)..=max_j {
result = result.min(1 + Solution::min_jumps(nums, j));
}
result
}
fn jump(nums: Vec<i32>) -> i32 {
Solution::min_jumps(&nums, 0)
}
}
The Rust details worth a closer look:
- Casts between
usizeandi32. Indexes areusize, butnums[i]is ani32, and Rust won't add the two. The sum is done ini32by castingiand the length withas i32, and the result is cast back withas usizeto be usable as a range end. Both casts are safe here, since the values are small and non-negative. minis a method.a.min(b)returns the smaller of two values of the same type. The chain(i as i32 + nums[i]).min(...)relies on parentheses so that the whole sum is the receiver.- Inclusive ranges.
(i + 1)..=max_jincludesmax_j. Ifnums[i]is 0,max_jequalsiand the range(i + 1)..=iis empty, so the loop doesn't run. - Borrowing.
numsis a shared reference,&Vec<i32>. Recursive calls pass it on without copying the vector, and many calls can read it at once. Solution::versusSelf::. Both name the same type inside theimplblock. The lesson spells itSolution::.- Length minus one.
nums.len() - 1is ausize. For an empty vector it would wrap in an optimized build (and panic in a debug one). The problem assumes at least one element.
Complexity
Time: exponential in the worst case. The function doesn't remember answers, so it recomputes the same cell many times. When every jump length is large, almost every subset of the cells in between is a distinct route. With a vector of length 20 whose elements are all 20, the function makes 524,288 calls. For length 25 it makes 16,777,216, so each extra cell doubles the work. For small inputs, like the example, which needs 11 calls, this is fast enough.
The backtracking version is the starting point. The cells' answers repeat, so storing each min_jumps(nums, i) after computing it, or working from the end of the vector backwards, brings the time down to O(n^2) (each cell looks at up to n landing cells), and a greedy scan that tracks the farthest reachable cell reaches O(n).
Space: O(n). The vector is borrowed, not copied. The recursion depth is at most n, because each call moves to a strictly larger index.
Edge cases and common mistakes
- One element.
[0]returns 0: the start is already the last cell. - Steps of 1.
[1, 1, 1, 1]returns 3, one jump per step. - One big jump.
[5, 1, 1, 1, 1, 1]returns 1, because the jump from index 0 reaches the end. The limitmin(..., last index)keeps the range from running past the vector. - Unreachable end. For
[1, 0, 1]the zero at index 1 blocks every route. The function returns 3, the starting value ofresult, and never a real jump count. The lesson's examples can all reach the end, but code that assumes that should be careful with this. - Empty vector.
nums[0]is out of bounds, and the program panics. - Counting the starting cell. The answer counts jumps, not cells visited. A route through three cells is 2 jumps.
- Leaving out the
1 +. Each jump has to be added, or every route would cost 0. - Starting the loop at
i. Landing on the same cell would recurse on the same call forever.
Testing
[2, 3, 1, 1, 4]gives2.[0]gives0.[1, 1, 1, 1]gives3.[5, 1, 1, 1, 1, 1]gives1.
