leetcode-greedy

45. Jump Game II.py

class Solution:
    def jump(self, nums: List[int]) -> int:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if maxi step we can jump befor index i is less than current index i, we need one more jump, and we choose longest jump we can do to minimize the number of jump.
                1.2. keep track max position the one could reach starting from the current index i or before it as longest jump when we needed
            2.How do determine our global solution? 
                At each step/index, num_jumps leads to our fewest number of jumps to there.
        T:O(n) because it's one pass along the input array
        S:O(1)
        """
        n = len(nums)
        # edge case
        if n == 0 or n ==1:
            return 0        
        # max position one could reach starting from index <= i 
        max_pos = nums[0]
        # max number of steps one could do inside this jump
        max_steps = nums[0]
        
        num_jumps = 1
        for i in range(1, n):
            # if to reach this point one needs one more jump
            if max_steps < i:
                num_jumps += 1
                max_steps = max_pos
            max_pos = max(max_pos, nums[i] + i)               
        return num_jumps