45. Jump Game II #

Problem #

Given an array of non-negative integers nums, 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.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^5

Problem Summary #

Given an array of non-negative integers, you are initially positioned at the first position of the array. Each element in the array represents the maximum length you can jump from that position. Your goal is to reach the last position of the array using the minimum number of jumps.

Solution Approach #

• To find the minimum number of jumps, it is natural to think of using a greedy algorithm to solve the problem. Scan the step array, maintain the current maximum index position that can be reached, recorded as the farthest reachable boundary. If the farthest boundary is reached during the scan, update the boundary and increment the number of jumps by 1.
• When scanning the array, there is actually no need to scan the last element, because before jumping to the last element, the farthest reachable boundary must be greater than or equal to the position of the last element; otherwise, you could not jump to the last element and reach the end. If you traverse to the last element, it means the boundary is exactly the last position, and the final number of jumps can simply be incremented by 1, so there is no need to access the last element.

Code #

package leetcode

func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	needChoose, canReach, step := 0, 0, 0
	for i, x := range nums {
		if i+x > canReach {
			canReach = i + x
			if canReach >= len(nums)-1 {
				return step + 1
			}
		}
		if i == needChoose {
			needChoose = canReach
			step++
		}
	}
	return step
}