Start learning free

LESSON 355 OF 414 · GREEDY

Jump Game in Scala: Minimum Jumps in O(n) with a Greedy Scan

Practice O(n) 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.
STEP 1 OF 8
    Ctrl + Enter to check

    SCALA · GREEDY

    Jump Game in Scala, explained

    Problem overview

    The method jump receives nums, an Array[Int] of non-negative integers. You start at index 0, and nums(i) is the farthest you can jump forward from index i. The method returns the minimum number of jumps needed to land on 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. A single jump from index 0 reaches at most index 2, so one jump is not enough.

    Approach: grow the reach one jump at a time

    A brute-force search would try every jump length from every index, and the number of paths grows quickly. The greedy idea avoids that by thinking in rounds. After k jumps there is a set of indices you could be standing on, and that set is always a block of consecutive indices from 0 up to some farthest index. You never need to track which exact index you're on, only how far the block reaches.

    The solution keeps two numbers:

    • curMax: the farthest index reachable with the jumps counted so far;
    • nextMax: the farthest index reachable with one more jump, starting from any index seen so far.

    The scan walks index by index. While i is still within curMax, the current jumps are enough to get there. Every index also updates nextMax with i + nums(i). When the scan reaches an index beyond curMax, one more jump is unavoidable. That jump starts from whichever earlier index reaches farthest, which is exactly what nextMax remembers, so curMax becomes nextMax.

    Trace [2, 3, 1, 1, 4]. Start with result = 1, curMax = 2 and nextMax = 2:

    • Index 1: it is within reach (2 >= 1). nextMax becomes max(2, 1 + 3) = 4.
    • Index 2: within reach. nextMax stays 4.
    • Index 3: beyond curMax (2 < 3). Count a second jump, result = 2, and set curMax = 4. Then nextMax stays 4.
    • Index 4: within reach (4 >= 4). nextMax becomes 8, which no longer matters.

    The method returns 2.

    Step by step

    1. Handle the trivial case. With one index or none, you're already on the last index, so return 0.
    2. Start result at 1. With at least two indices you need at least one jump, so that first jump is counted right away.
    3. Set curMax to nums(0). The first jump can take you as far as the first element allows.
    4. Set nextMax to nums(0) too. Index 0 is the only index seen so far, so it is the only starting point for a second jump.
    5. Loop over 1 until nums.length. This visits every index after the first, once each. The range excludes its end.
    6. Check whether index i is out of reach (curMax < i). If so, add a jump to result and set curMax to nextMax.
    7. Update nextMax for every index with math.max(nextMax, i + nums(i)). This runs even for the index that just triggered a jump, because that index can be where the following jump starts.
    8. End with result as the last expression, which Scala returns without return.

    The solution in Scala

    class Solution {
    def jump(nums: Array[Int]): Int = {
        if (nums.length <= 1) {
            return 0
        }
        var result = 1
        var curMax = nums(0)
        var nextMax = nums(0)
        for (i <- 1 until nums.length) {
            if (curMax < i) {
                result += 1
                curMax = nextMax
            }
            nextMax = math.max(nextMax, i + nums(i))
        }
        result
    }
}

    The Scala details worth a closer look:

    • return and last expressions. The early return 0 is allowed in a method body. The final result has no return because the last expression of a block is its value.
    • until versus to. 1 until nums.length stops before the length, which is the last valid index plus one. 1 to nums.length would include the length and fail with an ArrayIndexOutOfBoundsException.
    • Parameters are vals. You can't reassign nums, which is why the changing values live in their own vars.
    • Arrays use parentheses. nums(i) is a method call on the array, not a bracket index.

    Complexity

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

    Space: O(1). The solution keeps three integers and the loop index, whatever the size of the input.

    Edge cases and common mistakes

    • One element. [0] returns 0, because you start on the last index. An empty array returns 0 too.
    • A single big jump. [5, 1, 1, 1, 1] returns 1. The first jump already reaches past the end, so curMax is never smaller than i.
    • Steps of one. [1, 1, 1, 1] returns 3, one jump per step.
    • Zeros you can jump over. [2, 0, 1] returns 1: the first jump lands on the last index directly and never touches the 0.
    • Unreachable ends. The method assumes the last index can be reached. For [1, 0, 3] it returns 2 even though no sequence of jumps gets past the 0, so it doesn't report impossibility. A version that must handle such inputs needs an extra check on curMax and nextMax.
    • Forgetting the starting jump. Starting result at 0 undercounts every input of two or more elements by one.
    • Skipping the nextMax update on the index that triggers a jump. That index can start the next jump, so leaving it out can make later jumps too short.

    Testing

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