Jump Game II

Problem statement

Same jump rules as Jump Game, but now return the fewest jumps needed to land on the last index. Inputs are set up so a solution always exists.

Example:

Input:

[2, 3, 1, 1, 4]

Expected output:

2

Why: 0 → 1 → 4 uses two jumps.

Practice on LeetCode: Jump Game II

Golang Solution

func jump(nums []int) int {
    if len(nums) == 1 {
        return 0
    }
    res := 0
    i := len(nums)-1
    for i >= 0 {
        j := i
        currPos := i
        for j >= 0 {
            if j + nums[j] >= i {
                currPos = j
            }
            j -= 1
        }
        if currPos != i {
            res += 1
        }
        if currPos == 0 {
            break
        }
        i = currPos
    }

    return res
}