Sharing my python solution, O(N) Time and O(1) Space, simple to understand


  • 1
    class Solution(object):
        def canJump(self, nums):
            
            # Recursive
            # This works but it is slow and big, O(N^2) Time and O(N) Space
            
            def jump(nums, i):
                if i <= 0:
                    return True
                for j in range(i - 1, -1, -1):
                    if nums[j] + j >= i and jump(nums, j):
                        return True
                return False
                
            # Much better, iterative, O(N) Time and O(1) Space
            
            def jump_(nums):
                beg, end = 0, nums[0]
                while end < len(nums) - 1:
                    next_jump = 0
                    while beg <= end:
                        next_jump = max(next_jump, nums[beg] + beg)
                        beg += 1
                    if next_jump <= end:
                        return False
                    beg = end
                    end = next_jump
                return True
            
            return jump_(nums) if len(nums) >= 1 else False

Log in to reply
 

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