Problem #45: Jump Game II

Intuition & Strategy Breakdown

Use a greedy approach. Maintain the maximum reach attainable so far and the end boundary of the current jump step. Increment jumps when reaching the end boundary.

Python 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

Java Solution

class Solution {
    public int jump(int[] nums) {
        int res = 0, l = 0, r = 0;
        while (r < nums.length - 1) {
            int farthest = 0;
            for (int i = l; i <= r; i++) {
                farthest = Math.max(farthest, i + nums[i]);
            }
            l = r + 1;
            r = farthest;
            res++;
        }
        return res;
    }
}