Last updated on January 19th, 2025 at 10:55 pm

Here, we see a Jump Game II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming, Greedy

Level of Question

Medium

Jump Game II LeetCode Solution

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Greedy Algorithm. The code uses a greedy approach to minimize the number of jumps required to reach the end of the array by always jumping to the farthest reachable position at each step.

3. Code Implementation in Different Languages

3.1 Jump Game II 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;        
    }
};

3.2 Jump Game II 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.3 Jump Game II 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;    
};

3.4 Jump Game II 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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)

• The greedy approach ensures that the algorithm always makes the optimal choice at each step, minimizing the number of jumps.
• The implementation is efficient and works for all four languages with the same time and space complexity.