Simple Python O(n) time O(1) space


  • 0

    We can think of this problem as maximizing our jump distance at each interval. Since we have the option of stepping forward 0 to nums[i] steps at each index i, we just need to check the the furthest point reachable for each interval as we would have an option of visiting every index before that point. In my code lo and hi stands for the boundaries of each interval and these boundaries are updated to the next index from the previous hi and the new maximum point reachable, respectively.

    class Solution(object):
        def canJump(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if not nums: return False
            dest = len(nums)-1
            lo = hi = _max = 0
            while _max < dest:
                while lo <= hi:
                    _max = max(lo+nums[lo], _max); lo += 1 # lo++
                if _max <= hi: return False
                hi = _max
            return True
    

Log in to reply
 

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