Very Simple Python Code


  • 1
    L
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # key point is, if you can reach a point, you can reach any point before it
        # not hard to prove
        
        # either you find a path to the end
        # or you find a point where you cannot reach from any point below
        
        # p1 is the next point to search
        # p2 is the lowest idx you know from where you can go to the end
        p1, p2 = len(nums)-1, len(nums)-1
        while p1 >= 0:
            if p1 + nums[p1] >= p2:
                p2 = p1
            p1 -= 1
        return p2 == 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.