leetcode-greedy

55. Jump Game.py

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if max position the one could reach starting from the current index i or before less than current index i --> impossible to reach current index i from index < i. Clearly, it leads to impossible to reach the last index.
                
                1.2. keep track max position the one could reach starting from the current index i or before.
            2.How do determine our global solution? 
                At each step/index, we can reach. It leads to we can reach the last index.
                
        T:O(n) because it's one pass along the input array
        S:O(1)
        """
        n = len(nums)
        if n == 1:
            return True
        # max position one could reach starting from index <= i
        max_pos = nums[0] # base case for index 0
        for i in range(1, n):
            # if one could't reach this point
            if max_pos < i:
                # One couldn't reach index i if the maximum position that one could reach starting from the previous cells is less than i.
                return False
            # keep track max position the one could reach starting from the current index i or before.
            max_pos = max(max_pos, nums[i] + i)
        return True