Python Greedy O(n) time and O(1) space with explanation

  • 1

    The idea is basically:

    1. if there isn't any 0 between the start point and end point, then it's always true(right? since all are connected)
    2. if there are some 0s, then we need to check if we can possibly pass the 0s
    def canJump(self, nums):
            #The farthest index that I can reach so far
            maximum = 0
            #Go through the array
            for i in xrange(len(nums)):
                #if the current number is 0 (but not the last number), and the farthest index I can reach is less or equal to here
                #just return False
                if nums[i] == 0 and i!= len(nums)-1 and maximum <= i:
                    return False
                #update my farthest potential reach if possible
                maximum = max(maximum, i + nums[i])
            return True

Log in to reply

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