Jump Game II LeetCode Solution

Last updated on August 5th, 2024 at 03:15 am

Here, We see Jump Game II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Array, Dynamic Programming, Greedy

Level of Question

Medium

Jump Game II LeetCode Solution

Jump Game II LeetCode Solution

Problem Statement

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

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

1. Jump Game II LeetCode Solution C++

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), step = 0, start = 0, end = 0;
        while (end < n - 1) {
            step++; 
			int maxend = end + 1;
			for (int i = start; i <= end; i++) {
                if (i + nums[i] >= n - 1) return step;
				maxend = max(maxend, i + nums[i]);
			}
            start = end + 1;
            end = maxend;
        }
		return step;        
    }
};

2. Jump Game II LeetCode Solution Java

class Solution {
    public int jump(int[] nums) {
        final int size = nums.length;
        int destination = size-1;
        int curCoverage = 0, lastJumpIdx = 0;
        int timesOfJump = 0;
        if( size == 1 ){
            return 0;
        }
        for( int i = 0 ; i < size ; i++){
            curCoverage = Math.max(curCoverage, i + nums[i] );
            if( i == lastJumpIdx ){
                lastJumpIdx = curCoverage;
                timesOfJump++;
                if( curCoverage >= destination){
                    return timesOfJump;
                }
            }
        }
        return timesOfJump;        
    }
}

3. Jump Game II LeetCode Solution Javascript

var jump = function(nums) {
    const size = nums.length;
    let destination = size-1;
    let curCoverage = 0, lastJumpIdx = 0;
    let timesOfJump = 0;
    if( size == 1 ){
        return 0;
    }
    for( let i = 0 ; i < size ; i++){
        curCoverage = Math.max(curCoverage, i + nums[i] );
        if( i == lastJumpIdx ){
            lastJumpIdx = curCoverage;
            timesOfJump++;
            if( curCoverage >= destination){
                return timesOfJump;
            }
        }
    }
    return timesOfJump;    
};

4. Jump Game II LeetCode Solution Python

class Solution(object):
    def jump(self, nums):
        n, start, end, step = len(nums), 0, 0, 0
        while end < n - 1:
            step += 1
            maxend = end + 1
            for i in range(start, end + 1):
                if i + nums[i] >= n - 1:
                    return step
                maxend = max(maxend, i + nums[i])
            start, end = end + 1, maxend
        return step
Scroll to Top