Jump Game II medium

Problem Statement

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 from index 0 to 1, then 3 from index 1 to 4.

Example 2

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

Steps

The problem can be solved using a greedy approach. We maintain two pointers:

1. currentReach: The furthest index reachable with the current number of jumps.
2. maxReach: The furthest index reachable with the current number of jumps plus one.

We iterate through the array. For each index, we update maxReach to the maximum reachable index from that position. If we reach the currentReach, it means we've used up the current number of jumps, so we increment the jump count and update currentReach to maxReach.

Explanation

The algorithm works because at each step, we're greedily extending our reach as far as possible with the current number of jumps. By updating maxReach we explore all possible jumps from each position within the current jump's range. When we hit currentReach, we know we've exhausted the possibilities for the current jump count and need to make another jump.

Code

function jump(nums: number[]): number {
    let currentReach = 0;
    let maxReach = 0;
    let jumps = 0;

    for (let i = 0; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]); //Extend maxReach

        if (i === currentReach) { //If current jump is exhausted
            jumps++;
            currentReach = maxReach; //Start next jump from maxReach
            if (currentReach >= nums.length - 1) break; //optimization: if reached end already, break
        }
    }
    return jumps;
};

Complexity

• Time Complexity: O(N), where N is the length of the array. We iterate through the array once.
• Space Complexity: O(1). We use a constant number of variables.