Start learning free

LESSON 322 OF 338 · GREEDY

Jump Game in Go: Greedy Minimum Jumps in O(n)

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 7
    Ctrl + Enter to check

    GO · GREEDY

    Jump Game in Go, explained

    Problem overview

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

    For [2, 3, 1, 1, 4] the answer is 2. Jump 1 step from index 0 to index 1, then 3 steps from index 1 to the last index. No single jump works, because index 0 reaches at most index 2.

    Approach: widen the reach one jump at a time

    A brute-force search would try every jump length from every index, which blows up quickly. The greedy idea avoids that by thinking in layers instead of single positions.

    Say you have made some number of jumps. Those jumps can land you anywhere up to some index, the current reach. While you walk through the indices inside that reach, keep track of the farthest index that one more jump could reach from any of them, the next reach. When you step past the current reach, you must spend one more jump, and the best way to spend it is to have started it from whichever index gave the farthest next reach. So the next reach becomes the current reach.

    You never need to decide which exact index to jump from. You only need the best reach it could have given, and that is a single number.

    For [2, 3, 1, 1, 4] the values evolve like this:

    • Start: one jump counted, currentMax = 2, nextMax = 2.
    • Index 1: inside the reach. Its jump gives 1 + 3 = 4, so nextMax = 4.
    • Index 2: inside the reach. 2 + 1 = 3 doesn't beat 4.
    • Index 3: this is beyond currentMax = 2, so count a second jump and set currentMax = 4. Then 3 + 1 = 4 keeps nextMax at 4.
    • Index 4: inside the new reach. The loop ends with 2 jumps.

    Step by step

    1. Handle the trivial case. With at most one element you already stand on the last index, so return 0.
    2. Declare result as 1. With two or more elements at least one jump is needed, so it is counted right away.
    3. Declare currentMax as nums[0]. The first jump can reach no farther than that.
    4. Declare nextMax as nums[0] too. It is the farthest index any index seen so far could reach, and for now only index 0 has been seen.
    5. Loop from index 1 to the end, since index 0 is already accounted for.
    6. Check currentMax < i. If index i lies beyond the current reach, add a jump and move the reach to nextMax.
    7. Update nextMax with i+nums[i] if that is larger. This runs for every index, including the one that triggered a new jump, because that index can start the following jump.
    8. Return result.

    The solution in Go

    func jump(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }
    result := 1
    currentMax := nums[0]
    nextMax := nums[0]
    for i := 1; i < len(nums); i++ {
        if currentMax < i {
            result++
            currentMax = nextMax
        }
        nextMax = max(nextMax, i+nums[i])
    }
    return result
}

    Go details worth knowing:

    • := declares and infers the type. result := 1 makes an int, and so do the other two variables, because nums[0] is an int. An unused variable would be a compile error, but all of these are used.
    • There is no while. A for with an init, a condition and a post statement is the usual counting loop, and it is what drives the scan here.
    • max is a built-in since Go 1.21. It takes two or more values of the same ordered type, so no import and no hand-written helper is needed.
    • Slices carry their length. len(nums) <= 1 covers both the empty slice and the one-element slice before nums[0] is read. Without that check, an empty slice would panic with an index out of range.

    Complexity

    Time is O(n): the loop visits each index once and does a constant amount of work. Space is O(1): only three integers are kept, whatever the size of nums.

    Edge cases and common mistakes

    • One element. jump([]int{5}) returns 0. You are already at the end, whatever the value says.
    • A big first jump. For [4, 1, 1, 1, 1] the first jump covers every index, so the answer is 1. No later index triggers the currentMax < i branch.
    • Only small steps. For [1, 1, 1, 1] every index needs its own jump, and the answer is 3.
    • Counting a jump per index. A jump is counted only when the loop leaves the current reach, not each time nextMax grows.
    • Skipping the update on the triggering index. If nextMax were updated only in an else branch, the index that forced a new jump would never contribute its own reach.
    • Unreachable ends. The solution assumes the last index can be reached. For [1, 0, 1] it returns 2 even though the zero blocks the way, so the input must be guaranteed reachable.

    Testing

    These inputs are worth trying, with the results the solution gives:

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