LC045 - Jump Game II

Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and

• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example

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.

Solution

Greedy

Calculate jumps based on 'sections'. Each section consists of the indices that are reachable in one step from the current section. It is kind of like a BFS. Time complexity is $O(n)$ since we only need one pass through the entire array.

def jump(self, nums: List[int]) -> int:
	left = 0
	right = 0
	jumps = 0

	while right < len(nums) - 1:
		maxReach = 0
		for i in range(left, right + 1):
			maxReach = max(maxReach, i + nums[i])
		# new section
		left = right + 1
		right = maxReach
		jumps += 1
	return jumps