Start learning free

LESSON 288 OF 414 · BACKTRACKING

Jump Game in Scala: Recursion Over Every First Jump

Practice O(2n) 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:

Your algorithm should run in O(2^n) time and use O(n) extra space.

STEP 1 OF 7
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Jump Game in Scala, explained

    Problem overview

    The method jump receives an Array[Int] called nums. You start at index 0, and nums(i) is the longest jump you can make from index i: you may move to any index from i + 1 to i + nums(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: jump one step from index 0 to index 1, then three steps to index 4. No single jump can do it, because nums(0) is 2 and the last index is 4.

    Approach: try every first jump

    Ask a smaller question: what is the minimum number of jumps to the end if you are standing at index i? Call the answer minJumps(nums, i). Then:

    • if i is the last index, the answer is 0;
    • otherwise, you must choose a first jump to some index j in i + 1 to i + nums(i). That jump costs 1, and from j you need minJumps(nums, j) more. The answer is the best such choice.

    The recursion always moves to a larger index, so it always ends at the last index (or at a cell with nothing reachable).

    This lesson is the starting point for the problem. It tries every possibility, which is simple but slow: the same index is solved again and again. The other lessons on this problem build on it to reach the lower complexity.

    Step by step

    1. Call the helper from jump. The answer begins at index 0, so the body is just minJumps(nums, 0). As the final expression, its value is returned without a return.
    2. Declare minJumps(nums, i) with an Array[Int] and an Int, returning an Int.
    3. Base case: if i == nums.length - 1, return 0.
    4. Start the best answer at nums.length. No real path needs that many jumps (the most possible is nums.length - 1), so it acts as infinity. Declare it as a var, because it will be updated.
    5. Loop over the reachable cells. With var j = i + 1, a while loop runs as long as j < nums.length and j <= i + nums(i), and ends each pass with j += 1.
    6. Update the best answer: result = math.min(result, 1 + minJumps(nums, j)). One jump to j plus the best from there.
    7. Return result after the loop, as the final expression.

    The solution in Scala

    class Solution {
    def minJumps(nums: Array[Int], i: Int): Int = {
        if (i == nums.length - 1) {
            return 0
        }
        var result = nums.length
        var j = i + 1
        while (j < nums.length && j <= i + nums(i)) {
            result = math.min(result, 1 + minJumps(nums, j))
            j += 1
        }
        result
    }
    def jump(nums: Array[Int]): Int = {
        minJumps(nums, 0)
    }
}

    Scala details:

    • Two conditions in the loop. j < nums.length keeps the loop inside the array. j <= i + nums(i) keeps it inside the jump length. Without the first one, a big nums(i) near the end would read past the array and throw.
    • math.min is scala.math.min, reachable as math.min without an import. It works on Int values.
    • return only where needed. The base case uses an early return. The last expression, result, is the method's value.
    • var versus val. result and j change, so they are vars.
    • The big initial value. If no cell is reachable from some index, result keeps its starting value nums.length. The caller then computes 1 + nums.length, which is still larger than any real answer, so such a dead end never wins a comparison against a real path. It also can't overflow the way Int.MaxValue + 1 would.

    Complexity

    Time: exponential. Every call of minJumps spawns calls for each reachable index, and nothing is remembered. If every value is large, the number of calls doubles for each extra cell. For an array of n values, all equal to n, there are 512 calls when n is 10, 16,384 when n is 15, 524,288 when n is 20 and 8,388,608 when n is 24. In these cases the count is 2^(n - 1).

    Space: O(n). The recursion goes at most n calls deep, since each call moves to a larger index.

    The calls repeat work because many paths reach the same index. Remembering the answer per index brings the time down to O(n²): at most n answers, each found by a loop over at most n cells.

    Edge cases and common mistakes

    • Single cell. [0] returns 0, because you are already at the last index.
    • Steps of 1. [1, 1, 1, 1] returns 3. With all ones, each call has one reachable cell, so the work stays small: 24 calls for 24 values.
    • Unreachable end. This version has no special value for "impossible". For [3, 2, 1, 0, 4], every path gets stuck on the 0 at index 3, and the method returns 5, which is nums.length, not -1. For [0, 1] it returns 2. A result of nums.length or more means the last index can't be reached.
    • Forgetting the length check. A loop condition of only j <= i + nums(i) runs off the end of the array.
    • Starting j at i. A jump of length 0 would make the function call itself with the same index forever.
    • Taking the largest jump. Always jumping as far as possible is not always optimal. In [2, 3, 1, 1, 4] the best first jump is 1 step, not 2: jumping to index 2 (value 1) needs two more jumps, three in total.

    Testing

    • [2, 3, 1, 1, 4] gives 2.
    • [0] gives 0.
    • [1, 1, 1, 1] gives 3.
    • [5, 5, 5, 5, 5, 5] 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