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.

Javascript Solution

var jump = function(nums) {
    let farthest = 0
    let end = 0
    let ans = 0
    for(let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i])
        if(i === end) {
            end = farthest
            ans++
        }
    }
    return ans
};

TypeScript Solution

var jump = function(nums) {
    let farthest = 0
    let end = 0
    let ans = 0
    for(let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i])
        if(i === end) {
            end = farthest
            ans++
        }
    }
    return ans
};