Jump Game II

Greedy

20 min

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 ≤ j ≤ nums[i]
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can always reach nums[n - 1].

Example

Example 1:

Input: nums = [2,3,1,1,4]

nums: [2, 3, 1, 1, 4]

Output: 2

Solution

The greedy approach is to always make the jump that will take us the farthest. We maintain two pointers, `l` and `r`, representing the current jump's range. We iterate through this range to find the next farthest jump, and then we jump to that new range.

Algorithm Steps

Initialize `jumps` to 0, and `l` and `r` to 0.
While `r` is less than the last index:
Find the farthest jump possible from the current range `[l, r]`.
Update `l` to `r + 1` and `r` to the new farthest jump.
Increment `jumps`.
Return `jumps`.

Jump Game II

Greedy Approach

Input: nums = [2, 3, 1, 1, 4]

Output: 0

Progress1 / 1

Ready to start the visualization

Nums

Jumps

Farthest Reach

Jump Game II Solution


class Solution:
    def jump(self, nums: list[int]) -> int:
        res = 0
        l = r = 0
        
        while r < len(nums) - 1:
            farthest = 0
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])
            l = r + 1
            r = farthest
            res += 1
        return res