45 Jump Game II

You are given a 0-indexed array of integers nums of length n.
Each element nums[i] represents the maximum length of a forward jump from index i.

• At each position i, you may jump to any index i + j where:
  • 1 <= j <= nums[i] and
  • i + j < n.

Your goal is to reach the last index in the minimum number of jumps.
You can assume that it is always possible to reach the last index.

Return the minimum number of jumps to reach the last index.

---

Example 1:

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

Output:
2

Explanation:
The minimum jumps are:

• Jump 1 step from index 0 to index 1
• Jump 3 steps from index 1 to the last index

---

Example 2:

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

Output:
2

---

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It is guaranteed that you can reach the last index.

Solution:

We can solve this using a Greedy algorithm in O(n) time.

Idea:

We iterate through the array while keeping track of:

• farthest: the farthest point we can reach so far.

• end: the current jump boundary.

• ans: total jumps taken so far.

• Each time we reach the end of the current range (i == end),
  we increment the jump count and update the range to farthest.

Java Solution

class Solution {
    public int jump(int[] nums) {
        var farthest = 0;
        var end = 0;
        var ans = 0;
        for(var i = 0; i < nums.length; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if(i == end) {
                end = farthest;
                ans++;
            }
        }
        return ans;
    }
}

Kotlin Solution

class Solution {
    fun jump(nums: IntArray): Int {
        var farthest = 0
        var end = 0
        var ans = 0
        for(i in 0 until nums.lastIndex) {
            farthest = maxOf(farthest, i + nums[i])
            if(i == end) {
                end = farthest
                ans++
            }
        }
        return ans
    }
}

Golang Solution

func jump(nums []int) int {
    farthest, end, ans := 0, 0, 0
    for i := 0; i < len(nums) - 1; i++ {
        if i + nums[i] > farthest {
            farthest = i + nums[i]
        }
        if i == end {
            end = farthest
            ans += 1
        }
    }
    return ans
}