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