Python O(n) solution


  • 6
    B
    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
    E

    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.