Python solution with explanation


  • 0
    E

    We maintain a global farthest distance can be reached, reach, and a local farthest distance can be reached within the global reach.

    We update local everytime we go to a new position, which is indexed by pos.

    If we achieve global position, we look at local and update global=local.

    Continue until we reach the end of the list.

        def jump(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            step, reach, local, pos = 0, 0, 0, 0
            while reach < len(nums)-1:
                local = max(local, pos+nums[pos])
                if pos == reach and local > reach:
                    reach = local
                    step += 1
                pos += 1
            return step

Log in to reply
 

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