Python O(n) solution

  • 6
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def jump(self, nums):
            n, cur_max, next_max, steps = len(nums), 0, 0, 0
            for i in xrange(n):
                if i > cur_max:
                    steps += 1
                    cur_max = next_max
                    if cur_max >= n: break
                next_max = max(next_max, nums[i] + i)
            return steps

  • 0

    This solution is very fast!
    Instead of doing BFS, it just loop through the array and update cur_max and next_max on the fly.
    Thanks for sharing!

Log in to reply

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