Jump Game II

XXX.Jump Game II

Greedy

Problem Statement:

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, return the minimum number of jumps required to reach the last index. Assume you can always reach the last index.

Algorithm:

1. Initialize three variables:
   • jumps to count the number of jumps made.
   • currLadder to track the end of the current jump range.
   • maxLadder to track the farthest point reachable so far.
2. Iterate through the array:
   • If the current index exceeds maxLadder, return -1, as it's not possible to reach the last index.
   • When the current index exceeds currLadder, increment the jump count and update currLadder to maxLadder.
   • Update maxLadder to the maximum of its current value and i + nums[i].
3. Return jumps as the result.

Complexity:

Time: O(n), where n is the length of the array, as we iterate through the array once. | Space: O(1), as only constant extra space is used.

Java Implementation:

public int jump(int[] nums) {
    int jumps = 0;         // Number of jumps made
    int currLadder = 0;    // End of the current jump range
    int maxLadder = 0;     // Farthest point reachable so far

    for (int i = 0; i < nums.length; i++) {
        if (i > maxLadder) return -1; // Cannot proceed further

        // End of current ladder, make a jump
        if (i > currLadder) {
            jumps++;
            currLadder = maxLadder; // Update ladder to the farthest point
        }

        // Update the farthest point reachable
        maxLadder = Math.max(maxLadder, i + nums[i]);
    }

    return jumps; // Minimum number of jumps required
}
                

Python Implementation:

def jump(nums):
    jumps = 0         # Number of jumps made
    curr_ladder = 0   # End of the current jump range
    max_ladder = 0    # Farthest point reachable so far

    for i in range(len(nums)):
        if i > max_ladder:
            return -1 # Cannot proceed further

        # End of current ladder, make a jump
        if i > curr_ladder:
            jumps += 1
            curr_ladder = max_ladder # Update ladder to the farthest point

        # Update the farthest point reachable
        max_ladder = max(max_ladder, i + nums[i])

    return jumps # Minimum number of jumps required
                

C++ Implementation:

int jump(vector& nums) {
    int jumps = 0;         // Number of jumps made
    int currLadder = 0;    // End of the current jump range
    int maxLadder = 0;     // Farthest point reachable so far

    for (int i = 0; i < nums.size(); i++) {
        if (i > maxLadder) return -1; // Cannot proceed further

        // End of current ladder, make a jump
        if (i > currLadder) {
            jumps++;
            currLadder = maxLadder; // Update ladder to the farthest point
        }

        // Update the farthest point reachable
        maxLadder = max(maxLadder, i + nums[i]);
    }

    return jumps; // Minimum number of jumps required
}