Jump Game II (Deprecated)
Given a non-negative integer array where each index represents the maxmimum you can iterate forward, minimize the number of jumps to reach the end of the array. Tags: Greedy
Try It!
Discussion
Video
Solution
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
reachable = 0
last_jump_idx = 0
count = 0
for i in range(len(nums)):
# use greedy strategy
reachable = max(reachable, i + nums[i])
if i == last_jump_idx:
last_jump_idx = reachable
count += 1
if last_jump_idx == len(nums) - 1:
# if we land on last index but don't include this case, we add an extra jump
return count
return count