Start learning free

LESSON 297 OF 414 · MEMOIZATION

Jump Game in Scala: O(n^2) Iterative Dynamic Programming

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

    SCALA · MEMOIZATION

    Jump Game in Scala, explained

    Problem overview

    The method jump receives an array nums of non-negative integers. You start at index 0, and nums(i) is the longest jump allowed from index i. The method returns the minimum number of jumps needed 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. The statement asks for an iterative solution in O(n^2) time and O(n) extra space.

    Approach: fill the table from right to left

    The recursive memoized solution defines the answer for cell i in terms of cells to its right. Its first jump goes to some cell j with i < j <= i + nums(i), and the cost is 1 plus the answer for j. The iterative version uses the same relationship but fills a table instead of recursing.

    Let dp(i) be the minimum number of jumps from cell i to the last cell. The last cell needs 0 jumps. Every other dp(i) depends only on cells further right, so if you walk i from the second-to-last cell down to 0, every value you need is already final. There is no recursion, no cache lookups and no risk of a deep call stack.

    The table starts filled with n, the array length. A real path needs at most n - 1 jumps, so n acts as infinity: any real path beats it.

    Here is the table for nums = [2, 3, 1, 1, 4], so n = 5. It starts as [5, 5, 5, 5, 0]. At i = 3 the value is 1, so only cell 4 is reachable and dp(3) becomes 1 + 0 = 1. At i = 2 the only reachable cell is 3, giving dp(2) = 2. At i = 1 the value is 3, so cells 2, 3 and 4 are reachable. The values of 1 + dp(j) are 3, 2 and 1, and the best is jumping straight to cell 4, so dp(1) = 1. At i = 0 cells 1 and 2 are reachable; 1 + dp(1) = 2 beats 1 + dp(2) = 3, so dp(0) = 2.

    Step by step

    1. Store the length in n, and declare dp as Array.fill(n)(n): an array of size n with every entry set to n.
    2. Set dp(n - 1) to 0. You are already on the last cell, so no jumps are needed.
    3. Loop i over n - 2 to 0 by -1, which counts down and includes 0. Walking right to left guarantees that the cells i depends on are final.
    4. Visit the reachable cells with var j = i + 1 and a while loop running while j < n and j <= i + nums(i), ending its body with j += 1.
    5. Relax dp(i): a first jump to j costs 1 + dp(j), so keep the smaller of that and the current dp(i) using math.min.
    6. Finish with dp(0) as the last expression. It is the answer from the starting cell.

    The solution in Scala

    class Solution {
    def jump(nums: Array[Int]): Int = {
        val n = nums.length
        val dp = Array.fill(n)(n)
        dp(n - 1) = 0
        for (i <- n - 2 to 0 by -1) {
            var j = i + 1
            while (j < n && j <= i + nums(i)) {
                dp(i) = math.min(dp(i), 1 + dp(j))
                j += 1
            }
        }
        dp(0)
    }
}

    The Scala details worth a closer look:

    • Array.fill(n)(n) has two parameter lists: the first is the number of elements, the second is the value to put in each. It creates a new Array[Int] of size n filled with n.
    • Counting down. n - 2 to 0 by -1 is a Range that includes both ends and steps by -1. When n - 2 is below 0 the range is empty and the loop body never runs. until would exclude 0, which is why the loop uses to.
    • Arrays are mutable and fixed-size. dp(i) = ... updates an element in place. Indexing uses parentheses, and dp(n - 1) = 0 is a call to the array's update method.
    • The last expression is the result. There is no return; dp(0) is the value of the method body.
    • Ordinary loops. The while loop is needed because its upper bound, i + nums(i), is combined with an array-length check. A for over i + 1 to math.min(n - 1, i + nums(i)) would be the same.

    Complexity

    Time: O(n^2). The outer loop visits n - 1 cells, and for each the inner loop looks at up to n - 1 reachable cells. Each step does constant work.

    Space: O(n). Only the dp array grows with the input. Compared with the memoized recursion, it stores the same n answers without a map and without recursion frames.

    Edge cases and common mistakes

    • A single element. For [0], n - 2 is -1, so the loop doesn't run and dp(0) is the 0 set for the last cell. The answer is 0.
    • The example. [2, 3, 1, 1, 4] returns 2.
    • All ones. [1, 1, 1, 1] returns 3.
    • A jump bigger than the array. For [5, 0, 0, 0, 0, 0], the result is 1. The j < n test keeps the loop from reading past the end for larger numbers.
    • Unreachable end. In [1, 0, 3] the last cell can't be reached. The method returns n, here 3, because dp(0) keeps the "infinity" value. The lesson's tests don't use such arrays.
    • Going left to right. Filling dp from index 0 would read entries that are still at their starting value n, giving wrong answers.
    • Starting the table at 0. If dp were filled with zeros, math.min would always keep 0 and the answer would be 0.

    Testing

    • [2, 3, 1, 1, 4] gives 2.
    • [0] gives 0.
    • [1, 1, 1, 1] gives 3.
    • [5, 0, 0, 0, 0, 0] gives 1.
    • [2, 0, 1] gives 1.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free