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 step from index 0 to 1, then 3 steps to the last index.

Example 2

Input: nums = [1,1,1,1,1] Output: 4 Explanation: You need 4 jumps to reach the last index.

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 need to make another jump. We update the jump count and update currentReach to maxReach.
• We update maxReach to the maximum reachable index from the current position (i + nums[i]).

The algorithm continues until we reach or surpass the last index of the array. The final jump count is the minimum number of jumps required.

Code (C#)

using System;

public 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]); // Update max reachable index

            if (i == currentReach) { // If we've reached the current jump's limit
                jumps++;           // Increment jump count
                currentReach = maxReach; // Extend the reach to the new max
                if (currentReach >= n - 1) break; // Optimization: if we can reach the end, stop
            }
        }

        return jumps;
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the length of the nums array. We iterate through the array at most once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only need a few integer variables to track the jumps, current reach, and maximum reach.