Jump Game II - LeetCodee

Problem Description

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Examples

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 = [2,3,0,1,4]
Output: 2

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def jump(nums: List[int]) -> int:
    if len(nums) <= 1:
        return 0
    
    jumps = curr_max = next_max = 0
    
    for i in range(len(nums) - 1):
        next_max = max(next_max, i + nums[i])
        
        if i == curr_max:
            jumps += 1
            curr_max = next_max
            
            if currMax >= len(nums) - 1:
                break
    
    return jumps

Java Solution


class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        
        int jumps = 0;
        int currMax = 0;
        int nextMax = 0;
        
        for (int i = 0; i < nums.length - 1; i++) {
            nextMax = Math.max(nextMax, i + nums[i]);
            
            if (i == currMax) {
                jumps++;
                currMax = nextMax;
                
                if (currMax >= nums.length - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}

C++ Solution


class Solution {
public:
    int jump(vector& nums) {
        if (nums.size() <= 1) {
            return 0;
        }
        
        int jumps = 0;
        int currMax = 0;
        int nextMax = 0;
        
        for (int i = 0; i < nums.size() - 1; i++) {
            nextMax = max(nextMax, i + nums[i]);
            
            if (i == currMax) {
                jumps++;
                currMax = nextMax;
                
                if (currMax >= nums.size() - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if (nums.length <= 1) {
        return 0;
    }
    
    let jumps = 0;
    let currMax = 0;
    let nextMax = 0;
    
    for (let i = 0; i < nums.length - 1; i++) {
        nextMax = Math.max(nextMax, i + nums[i]);
        
        if (i === currMax) {
            jumps++;
            currMax = nextMax;
            
            if (currMax >= nums.length - 1) {
                break;
            }
        }
    }
    
    return jumps;
};

C# Solution


public class Solution {
    public int Jump(int[] nums) {
        if (nums.Length <= 1) {
            return 0;
        }
        
        int jumps = 0;
        int currMax = 0;
        int nextMax = 0;
        
        for (int i = 0; i < nums.Length - 1; i++) {
            nextMax = Math.Max(nextMax, i + nums[i]);
            
            if (i == currMax) {
                jumps++;
                currMax = nextMax;
                
                if (currMax >= nums.Length - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the array
Space Complexity: O(1) as we only use constant extra space

Solution Explanation

This solution uses a greedy approach to find the minimum number of jumps. Here's how it works:

Track two boundaries:
- currMax: farthest position reachable in current jump
- nextMax: farthest position reachable in next jump
For each position:
- Update nextMax with maximum reachable position
- When current position reaches currMax:
  - Increment jump count
  - Update currMax to nextMax

Key points:

Uses greedy approach
Maintains two boundaries
Only jumps when necessary
Guarantees minimum jumps