Jump Game II

Greedy Algorithm Medium

Python Java C++

def jump(nums):
    # Track current jumps needed
    jumps = 0
    # How far we can go with current jump count
    currLadder = 0
    # Maximum distance we can reach so far
    maxLadder = 0
    
    for i in range(len(nums)):
        # If we can't reach current position, jump is impossible
        if i > maxLadder: return -1
        
        # End of curr ladder, increment jumps
        if i > currLadder:
            jumps += 1
            currLadder = maxLadder
            
        # Update the furthest position we can reach
        maxLadder = max(maxLadder, i + nums[i])
    
    return jumps

public class Solution {
    public int jump(int[] nums) {
        // Track current jumps needed
        int jumps = 0;
        // How far we can go with current jump count
        int currLadder = 0;
        // Maximum distance we can reach so far
        int maxLadder = 0;
        
        for (int i = 0; i < nums.length; i++) {
            // If we can't reach current position, jump is impossible
            if (i > maxLadder) return -1;

            //End of curr ladder, increment jumps
            if (i > currLadder) {
                jumps++;
                currLadder = maxLadder;
            }
            
            maxLadder = Math.max(maxLadder, i + nums[i]);
        }
        return jumps;
    }
}

class Solution {
public:
    int jump(vector& nums) {
        // Track current jumps needed
        int jumps = 0;
        // How far we can go with current jump count
        int currLadder = 0;
        // Maximum distance we can reach so far
        int maxLadder = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            // If we can't reach current position, jump is impossible
            if (i > maxLadder) return -1;
            
            // End of curr ladder, increment jumps
            if (i > currLadder) {
                jumps++;
                currLadder = maxLadder;
            }
            
            maxLadder = max(maxLadder, i + nums[i]);
        }
        return jumps;
    }
};

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. Return the minimum number of jumps needed to reach the last index, or -1 if it's impossible to reach the end.

Detailed Explanation

Approach

This solution uses a "ladder" approach with fail-fast validation. We maintain two ladders: our current reach (currLadder) and maximum potential reach (maxLadder). We check for impossible jumps early and only increment our jump count when we exceed our current ladder's reach. This implementation differs from the standard Jump Game II by also handling cases where the end is unreachable.

Key Concepts

1. Impossible Jump Detection: If current position exceeds maxLadder, return -1
2. Current Ladder: Range we can reach with current number of jumps
3. Maximum Ladder: Furthest position we could potentially reach
4. Jump Increments: Only when we exceed current ladder's range

Algorithm Steps

1. Initialize tracking variables:
   • jumps = 0 (number of jumps needed)
   • currLadder = 0 (current reachable range)
   • maxLadder = 0 (maximum reachable position)
2. For each position i in the array:
   • If i > maxLadder, position is unreachable, return -1
   • If i > currLadder, increment jumps and extend currLadder to maxLadder
   • Update maxLadder based on current position's jump power
3. Return final jump count