45. Jump Game II

Intuition

The problem requires finding the minimum number of jumps needed to reach the last index of the array. Each element in the array represents the maximum jump length from that position. To solve this problem, we need to keep track of the farthest point that can be reached with the current number of jumps and determine when to make a jump to extend our reach.

Approach

1. Initialize three variables: - currentReach to keep track of the farthest index that can be reached with the current number of jumps, - currentMax to store the farthest index that can be reached in the next jump, - jumps to count the number of jumps made.
2. Iterate through the array up to the second last element: - For each position, update currentMax to be the maximum of currentMax and i + nums[i]. - If the current index i is equal to currentReach, increment jumps and update currentReach to currentMax.
3. Return the number of jumps.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are only using a few extra variables that do not scale with the input size.

Code

C++

class Solution {
public:
    int jump(vector& nums) {
        int n = nums.size();
        if (n == 1) return 0;
        
        int currentReach = 0;
        int currentMax = 0;
        int jumps = 0;
        
        for (int i = 0; i < n - 1; ++i) {
            if (i + nums[i] > currentMax) {
                currentMax = i + nums[i];
            }
            if (i == currentReach) {
                ++jumps;
                currentReach = currentMax;
            }
        }
        
        return jumps;
    }
};

Python

class Solution:
    def jump(self, nums: List[int]) -> int:
        dp = [10 ** 100] * len(nums)
        dp[0] = 0

        for i in range (len(nums)):
            num = nums[i]
            
            stop = min(i + num + 1, len(nums))
            for j in range(1, stop - i):
                dp[i + j] = min(dp[i + j], dp[i] + 1)
        return dp[-1]    

Java

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                min = Math.min(min, dp[i + j]);
            }
            dp[i] = min == Integer.MAX_VALUE ? min : min + 1;
        }
        return dp[0];
    }
}

JavaScript

var jump = function(nums) {
    let n = nums.length;
    if(n == 1) return 0;
    let currentReach = 0;
    let currentMax = 0;
    let jump = 0;
    for(let i =0; i < n-1; i++){
        if(i+nums[i] > currentMax){
            currentMax = i + nums[i];}
        if(i == currentReach){
            jump++;
            currentReach = currentMax;
            console.log(i, jump, currentReach)
        }}
    return jump;
};