45. Jump Game II

class Solution(object): def jump(self, nums): """ :type nums: List[int] :rtype: int """ curr = 0 # index of current position prev_furthest = 0 # previous furthest. Used as the start point+1 in the for loop. Save some iterations curr_furthest = curr + nums[curr] # index of current furthest position. Used as the end point of the for loop step = 0 while(curr_furthest < len(nums)-1): max_distance = 0 # placeholder: how far can we jump? next_pos = -1 # placeholder: where to jump next? # this loop compares all possible jump positions and select the one with biggest coverage for pos in range(prev_furthest+1, curr_furthest+1, 1): # why starts from prev_furthest instead of curr? Because if there is overlap, then the elements # greater than curr and smaller than prev_furthest must not have been chosen, or it will be chosen # in the last round already. Draw a picture if nums[pos] + pos - curr > max_distance: next_pos = pos max_distance = nums[pos] + pos - curr # the loop ends early when max_distance is zero and we have not reached the end if (max_distance == 0 and curr_furthest < len(nums)-1): return -1 # after the loop, we really make the jump by updating variables step += 1 curr = next_pos prev_furthest = curr_furthest curr_furthest = curr + nums[curr] if (curr == len(nums)-1): # no last jump return step else: # the last jump return step + 1