Leetcode Jump Game II Problem Solution

In this Leetcode Jump Game II Problem Solution 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].

Problem solution in Python.

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        i, j, k = 0, nums[0], 1
        while j < len(nums) - 1:
            i, j, k = j, max(j + nums[j] for j in range(i + 1, j + 1)), k + 1
        return k

Problem solution in Java.

import java.util.*;
class Solution {
    
    public int jump(int[] nums) {
        Vector<Integer> vector = new Vector<>();
        for (Integer el: nums) {
            vector.add(el);
        }
 
        return jumpMin(vector);
    }
    
    
    public static int jumpMin(Vector<Integer> vector) { //   vector[] : {1, 3, 6, 1, 0, 9};
        int l = vector.size();
        int jumps = 0;
 
        int maxCovered = 0;
        int currentMaxCovered = 0;
 
        for (int i = 0; i < l - 1; i++) {
            maxCovered = Math.max(maxCovered, i + vector.get(i));
 
            if (i == currentMaxCovered) {
                currentMaxCovered = maxCovered;
                jumps += 1;
            }
        }
        return jumps;
    }
    
  
 
}

Problem solution in C++.

int jump(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return 0;
    
    int count = 1, i = 0, j = 0, mx_idx = 0;
    
    while (i+nums[i] < n-1) {
        j = i; mx_idx = j;
        while (j <= i+nums[i] && j < n) {
            if (mx_idx + nums[mx_idx] < j + nums[j])
                mx_idx = j;
            j++;
        }
        
        i = mx_idx;
        count++;
    }
    
    return count;
}
 
};

Problem solution in C.

int jump(int* nums, int numsSize){
    int i;
    int newLastIndex = numsSize-1;
    int jumps=0;
    
    while (newLastIndex) { 
        for (i=0;i<newLastIndex;i++) { /* Farthest index from which newLastIndex is reachable*/
            if (nums[i]+i >= newLastIndex) {
                jumps++;
                newLastIndex=i;
                break;
            }
        }
    }
    return jumps;
}