O(n) solution in Python


  • 0
    H
    class Solution(object):
        def canJump(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            n = len(nums)
            cur_max, next_max = 0, 0
            for i in xrange(n):
                if cur_max < i: # if cur_max is less than 'i', we jump to next_max
                    cur_max = next_max
                    if cur_max < i: # if cur_max is still less than 'i', it means 'i' can never be reached
                        break
                next_max = max(i+nums[i], next_max) # update next_max using 'i'
            
            return False if cur_max < n-1 else True
    

Log in to reply
 

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