Five-line Python O(n) solution

  • 0

    It's an O(n) BFS, computing the range [near, far) which could be reached in step steps.

    class Solution(object):
        def jump(self, nums):
            near, far, step = 0, 1, 0
            while far < len(nums):
                nfar = max( i + j for i, j in zip( range(near, far), nums[near:far] ) ) + 1
                near, far, step = far, nfar, step + 1
            return step

Log in to reply

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