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]. The goal is 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 to the last index. The statement asks for O(n^2) time and O(n) extra space, and tells you to apply memoization to the plain recursive solution.
Approach: minimum over the first jump
Define min_jumps(i) as the minimum number of jumps needed to reach the last index starting from index i. Then:
- at the last index it is 0;
- anywhere else it is 1 plus the best of
min_jumps(j)over every indexjthat one jump fromican reach, fromi + 1up toi + nums[i](but never past the last index).
Without a cache, the recursion reaches the same index along many different routes and recomputes it each time. The running time explodes. The answer for an index doesn't depend on how you got there, so it can be stored the first time and reused. With the cache there are at most n distinct questions, and each one loops over at most n candidate jumps, which gives O(n^2).
On [2, 3, 1, 1, 4], min_jumps(0) can jump to index 1 or index 2. From index 1 the last index is within reach, so min_jumps(1) is 1 and the first route costs 2. From index 2 you must go through index 3, which makes min_jumps(2) equal to 2 and that route costs 3. The minimum is 2.
Step by step
- Create the cache in
jumpas a mutablestd::collections::HashMap. The helper fills it, and the key and value types come from the helper's signature. - Start from index 0 by making
Solution::min_jumps(&nums, 0, &mut cache)the final expression. - Declare the helper with the vector as
&Vec<i32>, the index asusizeand the cache as&mut HashMap<usize, i32>, returning ani32. - Base case: at the last index return 0.
- Cache hit: if the map has an answer for
i, return it. - Start with a large value.
resultbegins atnums.len(). A real path never needs that many jumps, so any real answer replaces it. - Find the reach.
max_jis the smaller ofi + nums[i]and the last index, computed ini32and converted back tousize. - Try each landing index
jfromi + 1tomax_j, keeping the smaller ofresultand1 + min_jumps(j). - Store and return. Insert
resultunderi, then return it.
The solution in Rust
impl Solution {
fn min_jumps(
nums: &Vec<i32>,
i: usize,
cache: &mut std::collections::HashMap<usize, i32>,
) -> i32 {
if i == nums.len() - 1 {
return 0;
}
if let Some(&v) = cache.get(&i) {
return v;
}
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, cache));
}
cache.insert(i, result);
result
}
fn jump(nums: Vec<i32>) -> i32 {
let mut cache = std::collections::HashMap::new();
Solution::min_jumps(&nums, 0, &mut cache)
}
}
The Rust details worth a closer look:
- Casts between integer types.
nums[i]is ani32, whileiandlen()areusize. Rust never mixes them implicitly, somax_jis computed ini32withas i32and converted back withas usizefor use in the range. The result is never negative here, so the final cast is safe. - Min with a method.
a.min(b)is a method on integers that returns the smaller value. It avoids anifand keeps the loop body to one line. - The inclusive range.
(i + 1)..=max_jincludesmax_j. Whennums[i]is 0,max_jequalsiand the range is empty, so the loop body never runs. - Reading the cache.
cache.get(&i)returns anOption<&i32>. The patternSome(&v)copies the number out, which ends the borrow beforecacheis used mutably again. - Passing borrows on. Inside the helper,
numsandcacheare already references, so the recursive call passes them by name. The mutable borrow ofcacheis lent to each call in turn and returned when it finishes. - The path to HashMap. The solution writes the full path
std::collections::HashMapin both places. Auseline at the top of a file would let you write justHashMap.
Complexity
Time: O(n^2). Each index is computed once, because later requests hit the cache. A computation loops over up to n - 1 landing indices, and each iteration is a lookup or a constant amount of work.
Space: O(n). The cache holds up to one entry per index. The recursion can go as deep as n calls, when every jump is 1 step long, so the call stack is also O(n).
Edge cases and common mistakes
- A single element.
[0]starts on the last index, so the answer is 0. - All ones.
[1, 1, 1, 1]needs 3 jumps, one per step. - One big first jump.
[3, 0, 0, 0]reaches the end in 1 jump even though the cells in between are zeros. - A zero that blocks the way. The statement doesn't say what to return when the end can't be reached. This code returns
nums.len()in that case:[1, 0, 5]gives 3. - Empty input. An empty vector isn't valid. The code computes
nums.len() - 1on ausize, and then indexing position 0 panics with an out-of-bounds error. - Forgetting the cache insert. The answers are still right but the running time grows exponentially.
- Jumping past the end. Without the
minagainst the last index, the loop would index outside the vector and panic.
Testing
[2, 3, 1, 1, 4]gives 2.[0]gives 0.[1, 1, 1, 1]gives 3.[3, 0, 0, 0]gives 1.[5, 1, 1, 1, 1, 1, 1]gives 2.
