LESSON 355 OF 414 · GREEDY

Jump Game in Rust: Minimum Jumps with a Greedy Scan

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.

STEP 1 OF 10

Guided

Ctrl + Enter to check

RUST · GREEDY

Jump Game in Rust, explained

Problem overview

The function jump receives a vector of non-negative integers, nums. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any smaller jump is allowed too. The function returns the minimum number of jumps needed to land on the last index.

For nums = [2, 3, 1, 1, 4] the answer is 2. Jump one step from index 0 to index 1, whose value is 3, then jump three steps to index 4. Jumping two steps to index 2 first would be slower, because index 2 only holds a 1. The tests assume the last index can always be reached.

Approach: reach, and the reach of one more jump

A brute-force search tries every possible landing spot at every jump, and the number of paths grows quickly. A dynamic-programming version stores the best jump count for each index and updates up to nums[i] later indices from every index, which is O(n²) in the worst case. A greedy scan does the work in a single pass.

The idea is to think in layers. After k jumps there is a farthest index you can have reached, and every index up to it is reachable in at most k jumps. Call that boundary cur_max. While scanning, you also track next_max, the farthest index that any index seen so far could reach with one more jump.

When the scan arrives at an index i that is beyond cur_max, the current jumps can't get there. One more jump is unavoidable, and the best place to have jumped from is whichever earlier index reaches farthest, which is exactly what next_max remembers. So the jump count goes up by one and cur_max becomes next_max.

Take nums = [2, 3, 1, 1, 4]:

Start: result = 1, cur_max = 2, next_max = 2. The first jump is counted from the start and covers indices 1 and 2.
i = 1: inside the reach. next_max becomes max(2, 1 + 3) = 4.
i = 2: inside the reach. next_max stays 4.
i = 3: cur_max = 2 < 3, so a second jump is needed. result = 2 and cur_max = 4.
i = 4: inside the new reach, so the scan ends with result = 2.

Step by step

Handle short vectors first. With zero or one element there is nothing to jump over, so the answer is 0. This check also keeps nums[0] in the next steps from panicking on an empty vector.
Start result at 1i32. With two or more elements at least one jump is needed, and the first one is counted right away. The i32 suffix matches the return type.
Set cur_max to nums[0] as usize. The first jump reaches at most this index. It is a usize because it will be compared with loop indices.
Set next_max to the same value. Before the scan has seen anything else, index 0 is the only starting point for the next jump.
Loop over 1..nums.len(). Index 0 is already accounted for in the initial values, so the scan visits every later index once.
Check whether the index is out of reach. If cur_max < i, add a jump and move the boundary to next_max.
Update next_max for every index, including the one that just triggered a jump, since that index may be the launch point of the following jump.
Return result as the final expression, without a semicolon.

The solution in Rust

impl Solution {
    fn jump(nums: Vec<i32>) -> i32 {
        if nums.len() <= 1 {
            return 0;
        }
        let mut result = 1i32;
        let mut cur_max = nums[0] as usize;
        let mut next_max = nums[0] as usize;
        for i in 1..nums.len() {
            if cur_max < i {
                result += 1;
                cur_max = next_max;
            }
            next_max = next_max.max(i + nums[i] as usize);
        }
        result
    }
}

The Rust details worth a closer look:

Casts and precedence. In i + nums[i] as usize, the as cast binds tighter than +, so only nums[i] is converted and the sum is a usize. Rust never mixes integer types in one expression. A negative i32 would wrap to a huge usize in an as cast, which is why the non-negative guarantee matters.
max is a method. next_max.max(x) returns the larger of two values of the same ordered type. There is no need for an if or a free function.
Mutable bindings. result, cur_max and next_max change during the scan, so they are declared with let mut. Without mut, the compiler rejects the assignments.
The range 1..nums.len() excludes its upper bound, so the last valid index is visited and nothing out of bounds is. Indexing a vector outside its length panics.

Complexity

Time: O(n). The loop touches each index once and does a constant amount of work per index.

Space: O(1). The function keeps three integers, however long nums is.

Edge cases and common mistakes

One element. [5] returns 0: you already stand on the last index. The early return handles it before the code reads anything.
Two elements. [5, 1] returns 1. The initial result = 1 is the first jump, and the loop never needs to add another.
Counting the first jump twice. Starting result at 0 and also counting a jump at the start of the loop gives answers one too large.
Updating cur_max on every index. The boundary may only move when the scan runs past it. Moving it earlier would count jumps that aren't needed.
Skipping the next_max update on the jump index. The index where the scan runs out of reach can itself be the best launch point.
An unreachable end. The tests assume the last index is reachable. For [0, 1] this code returns 2 instead of reporting a failure, so it isn't a reachability check.

Testing

[2, 3, 1, 1, 4] gives 2.
[1, 1, 1, 1] gives 3.
[5, 1, 1] gives 1.
[3, 1, 1, 1, 1] gives 2.
[1, 3, 1, 1, 1, 1] gives 3.
[7] gives 0.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free