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

1. Initialization: We initialize jumps to 0 (the number of jumps taken) and currentReach to 0 (the farthest index reachable with the current number of jumps). We also initialize maxReach to 0 (the farthest index reachable in the next jump).

2. Iteration: We iterate through the nums array.

3. Jump Check: For each index i, if i exceeds currentReach, it means we need to make another jump. We increment jumps, update currentReach to maxReach, and reset maxReach to 0.

4. Max Reach Update: We update maxReach to the maximum reachable index from the current position (i + nums[i]).

5. Termination: The loop continues until we reach the last index of the array. The final value of jumps represents the minimum number of jumps.

Explanation

The algorithm uses a greedy approach. At each step, it tries to reach the farthest possible index with the current jump. This ensures that we are always making optimal jumps to minimize the total number of jumps. The variables currentReach and maxReach help keep track of the reachable indices at each step.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    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 = max(maxReach, i + nums[i]); // Find the farthest reachable index

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

    return jumps;
}

int main() {
    vector<int> nums1 = {2, 3, 1, 1, 4};
    cout << "Minimum jumps for nums1: " << jump(nums1) << endl; // Output: 2

    vector<int> nums2 = {2, 3, 0, 1, 4};
    cout << "Minimum jumps for nums2: " << jump(nums2) << endl; // Output: 2

    return 0;
}

Complexity

• 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.