Start learning free

LESSON 258 OF 338 · BACKTRACKING

Jump Game in Go: Minimum Jumps by Recursion

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(n^2) time and use O(n) extra space.

STEP 1 OF 7
    Ctrl + Enter to check

    GO · BACKTRACKING

    Jump Game in Go, explained

    Problem overview

    The function jump(nums) receives a slice of non-negative integers. You start at index 0, and nums[i] is the longest jump you can make from index i: any distance from 1 to nums[i] is allowed. The function returns the minimum number of jumps that reaches the last index.

    For nums = [2, 3, 1, 1, 4] the answer is 2. Jump one step from index 0 to index 1, then three steps from index 1 to the last index, 4. No single jump from index 0 reaches the end, since the longest is 2.

    Approach: try every first jump

    This lesson uses the most direct idea. Define minJumps(nums, i) as the minimum number of jumps needed to reach the last index starting from index i. The answer to the problem is minJumps(nums, 0).

    For any i other than the last index, the first jump goes to some index j between i + 1 and i + nums[i]. A path whose first jump lands on j costs one jump plus the best path from j, which is 1 + minJumps(nums, j). Trying every j and keeping the smallest total gives the best path from i. This is backtracking: explore every choice, let the recursion solve what remains, and keep the best result.

    The recursion always moves to a larger index, so it must end. It stops at the last index, which needs 0 more jumps.

    The cost of this approach is large. Many paths pass through the same index, and each time the answer is recomputed from scratch. When every element is big enough to reach the end, the call count doubles with each extra element: 512 calls for 10 elements, 16,384 for 15 and 16,777,216 for 25. The work is exponential. Caching the answer for each index brings it down to O(n²), and a greedy scan brings it to O(n). The other lessons on this problem build those.

    Step by step

    1. Delegate. jump returns minJumps(nums, 0), since the journey starts at index 0.
    2. Declare the helper. minJumps takes the slice and the current index i and returns an int.
    3. Base case. If i is the last index, len(nums) - 1, the answer is 0.
    4. Create the running minimum. Declare result with := and set it to len(nums). No path needs that many jumps, because at most len(nums) - 1 are ever useful, so it works as infinity.
    5. Loop over the landing spots. Let j run from i + 1 while j < len(nums) and j <= i + nums[i]. The first condition keeps the loop inside the slice, and the second respects the jump length.
    6. Keep the better path. For each j, set result to the smaller of itself and 1 + minJumps(nums, j).
    7. Return result after every first jump has been tried.

    The solution in Go

    func jump(nums []int) int {
    return minJumps(nums, 0)
}

func minJumps(nums []int, i int) int {
    if i == len(nums)-1 {
        return 0
    }
    result := len(nums)
    for j := i + 1; j < len(nums) && j <= i+nums[i]; j++ {
        result = min(result, 1+minJumps(nums, j))
    }
    return result
}

    Go details worth knowing:

    • The for loop with two conditions. Go has only for, and its condition can be any boolean expression. Here j < len(nums) && j <= i+nums[i] stops at the end of the slice or at the end of the jump range, whichever comes first.
    • Built-in min. Since Go 1.21, min is part of the language and works on ordered types such as int. No import is needed.
    • Helpers in any order. jump calls minJumps before the file declares it, which Go allows at package level.
    • Slices travel cheaply. Each recursive call copies only the slice header, not the elements, and nothing in the function modifies nums.

    Complexity

    Time: exponential in the worst case, up to 2^(n-1) calls for a slice of length n where each element can reach the end. The loop tries every landing spot, and there is no memory of earlier answers.

    Space: O(n) for the call stack. Each call moves to a larger index, so the recursion is at most n frames deep.

    Edge cases and common mistakes

    • One element. [0] starts on the last index, so the answer is 0.
    • Zeros. An element 0 in the middle is a dead end, because the loop has no landing spots there and result keeps its large starting value. The recursion then ignores that branch unless the other branches are worse. For [2, 0, 0] the answer is 1, because jumping two steps straight from index 0 skips both zeros.
    • Unreachable end. If no path reaches the last index, as in [1, 0, 2], the function returns 3, which is len(nums) rather than a real count. The lesson's inputs always have a path.
    • Going past the end. Without the j < len(nums) check, a large nums[i] would send the loop beyond the slice.
    • Using the full jump. The value nums[i] is a maximum. Any shorter jump is allowed too, which is why the loop tries every distance.
    • Starting result at 0. The minimum would then always stay 0.

    Testing

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