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 and Explanation

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

1. currentReach: The farthest index we can reach with the current number of jumps.
2. maxReach: The farthest index we can reach in total.

We iterate through the array. For each index i:

• If i exceeds currentReach, it means we've used up all the jumps in the current phase and need to take another jump. We increment the jump count. The new currentReach becomes maxReach, allowing us to explore further.
• We update maxReach to the maximum reachable index from the current position (i + nums[i]).

The algorithm continues until we reach or exceed the last index. The final jump count is the minimum number of jumps needed.

Code (Java)

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0; // Already at the end or only one element

        int jumps = 0;
        int currentReach = 0;
        int maxReach = 0;

        for (int i = 0; i < n - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]); //Farthest we can reach from current position

            if (i == currentReach) { //If we've reached the limit of current jump
                jumps++;             //Take another jump
                currentReach = maxReach; //Update the current reach
                if (currentReach >= n - 1) break; //Optimization: if we can reach the end, break
            }
        }
        return jumps;
    }
}

Complexity Analysis

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