Medium

Jump Game II

LAB

Given max jump lengths, return the minimum number of jumps needed to reach the last index.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    3,
    1,
    1,
    4
  ]
}

Output
2

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

This is a very similar question to the first, we just want the number of jumps instead of a boolean feasibility check. It's the same greedy idea, we just need to track updates.

Reveal reference solution +

pythonREFERENCE

# greedy
# say you can reach indicies 0 up to e.
# in that interval, we find the furthest we can jump to = max
# when reach e, update interval to [0, max]
# number of updates is the answer

def jump(self, nums: List[int]) -> int:
    n, e, max_, res = len(nums), 0, 0, 0

    for i in range(n-1):
        max_ = max(max_, i + nums[i])
        if i == e:
            e = max_
            res += 1

    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗