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