A linear python solution


  • 0
    K

    Scan linearly, we only scan as far as we are allowed (second while condition), and we always jump greedily (second if condition);

    class Solution(object):
        def jump(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 1:
                return 0
            sln = []
            i = 0
            step = i
            maxCur = i + nums[i]
            maxNext = maxCur
            while i < len(nums):
                while i <= min(maxCur, len(nums)-1):
                    if i + nums[i] > maxNext:
                        maxNext = i + nums[i]
                        step = i
                    i = i + 1
                maxCur = maxNext
                sln.append(step)
            return len(sln)
    

Log in to reply
 

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