Start learning free

LESSON 300 OF 414 · MEMOIZATION

Jump Game in Rust: Minimum Jumps with Bottom-Up DP, O(n^2)

Practice O(n2) - DP Read the full explanation

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.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    RUST · MEMOIZATION

    Jump Game in Rust, explained

    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. The task is the minimum number of jumps to reach the last index.

    For [2, 3, 1, 1, 4] the answer is 2: one step from index 0 to index 1, then three steps to the last index. This lesson converts the memoized recursion of the previous one into a loop. It keeps the O(n^2) time and O(n) extra space.

    Approach: fill a table from the right

    Let dp[i] be the minimum number of jumps needed to reach the last index from index i. The recursive version asked for these values on demand and cached them. The iterative version computes every one of them in an order that guarantees the values it depends on are ready.

    The recurrence is the same: dp[last] is 0, and for any other index, dp[i] is 1 plus the smallest dp[j] among the indices j that a jump from i can land on. Every such j is to the right of i, so if the loop walks from the right end towards index 0, every dp[j] is final by the time dp[i] needs it. There is no recursion, so deep inputs can't overflow the call stack.

    On [2, 3, 1, 1, 4] the table fills as follows: dp[4] = 0. Index 3 can reach index 4, so dp[3] = 1. Index 2 can reach only index 3, so dp[2] = 2. Index 1 can reach indices 2, 3 and 4, and the best is index 4, so dp[1] = 1. Index 0 can reach indices 1 and 2, and the better is index 1, so dp[0] = 2.

    Step by step

    1. Allocate the table. Store the length in n, then create dp with vec![n as i32; n]. Every entry starts at n, which is larger than any real answer (at most n - 1 jumps), so it works as infinity until a path is found.
    2. Set the base. The last index needs no jumps: dp[n - 1] = 0.
    3. Walk right to left with for i in (0..n - 1).rev(), from index n - 2 down to 0.
    4. Find the reach. max_reach is i + nums[i] as usize, capped at n - 1 with .min.
    5. Try each landing index j in (i + 1)..=max_reach and update dp[i] to the smaller of itself and 1 + dp[j].
    6. Return dp[0] as the final expression.

    The solution in Rust

    impl Solution {
    fn jump(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![n as i32; n];
        dp[n - 1] = 0;
        for i in (0..n - 1).rev() {
            let max_reach = (i + nums[i] as usize).min(n - 1);
            for j in (i + 1)..=max_reach {
                dp[i] = dp[i].min(1 + dp[j]);
            }
        }
        dp[0]
    }
}

    The Rust details worth a closer look:

    • Repeating a value. vec![x; n] builds a vector of n copies of x. The cast n as i32 is needed because n is a usize and the entries are i32.
    • Reversing a range. 0..n - 1 excludes n - 1, and .rev() iterates it backwards, so i takes the values n - 2, n - 3, ... 0. For n = 1 the range is empty and the loop never runs, which is right: the answer is already dp[0] = 0.
    • Cast precedence. In i + nums[i] as usize, the cast applies to nums[i] first, and then the sum is of two usize values. The elements are non-negative, so the cast keeps their value. A negative i32 would turn into a huge usize.
    • Capping the reach. Without .min(n - 1), dp[j] would index past the end of the vector and panic.
    • Updating in place. dp[i] = dp[i].min(1 + dp[j]) reads and writes the same element. That is fine for i32, which is Copy, and the read finishes before the write.
    • The tail expression. dp[0] has no semicolon, so its value is returned.

    Complexity

    Time: O(n^2). The outer loop runs n - 1 times and the inner loop covers up to n - 1 landing indices, each with constant work. The worst case is a vector of large values, where every index can reach the end.

    Space: O(n). The table dp has one entry per index. Nothing else grows with the input.

    Edge cases and common mistakes

    • A single element. [0] gives 0.
    • Zeros in the middle. [3, 0, 0, 0] gives 1: the zeros are only a problem if the path has to land on them.
    • An unreachable end. The statement doesn't say what to return. This code leaves dp[0] at n in that case: [1, 0, 5] gives 3.
    • Empty input. An empty vector isn't a valid input. The expression dp[n - 1] would use 0usize - 1, which in an optimized build wraps and then indexes out of bounds.
    • Looping left to right. The table entries to the right would still hold the starting value n when they are read, and the answers would be wrong. On [2, 3, 1, 1, 4] such a loop returns 5 instead of 2, because the entries it reads have not been computed yet.
    • Starting the table at 0. A starting value of 0 would win every min, so the result would always be 0. The large starting value is what lets real counts replace it.

    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.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free