Python, O(n) time O(1) space, 12 lines of code, beats 97.41%

  • 1

    The idea is to find the right most boundary which one can reach using current number of jumps.
    Then increase the number of jumps by 1 and then search for new right most boundary. And so on.
    Since every element in the array is visited once, it is linear time O(n) and constant space O(1).

    def jump(self, nums):
        jump = 0 # number of jumps
        pb, cb = 0, 0 # Previous and Current right-most Boundary
        i = 0 # index
        while cb < len(nums)-1:
            while i <= pb: # search to find the right-most boundary using current number of jumps
                if i + nums[i] > cb:
                    cb = i + nums[i]
                i += 1
            jump += 1 
            pb = cb
        return jump


Log in to reply

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