Jump Game II In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement – Jump Game II

You are given an array of non-negative integers nums where each element in the array represents your maximum jump length from that position. Your goal is to reach the last index starting from the first index using the minimum number of jumps. You can assume that you can always reach the last index.

Example:

Input:

nums = [2, 3, 1, 1, 4]

Output:

2

Explanation: Jump from index 0 to 1 (nums[0] = 2), then jump from index 1 to 4 (nums[1] = 3).

Approach:

We are asked to minimize the number of jumps. The optimal approach for this problem is Dynamic Programming (DP) where we keep track of the minimum jumps required to reach each index in the array.

Dynamic Programming Explanation:

1. Initialization:
   • Define an array dp where dp[i] represents the minimum number of jumps to reach index i.
   • Set dp[0] = 0 (since no jump is needed to reach the first index).
   • For all other indices, initialize dp[i] to a large value (infinity) as we haven’t computed the number of jumps for them yet.
2. Transition:
   • Loop through each index i, and for each index, check all subsequent indices j that can be reached from i (i.e., nums[i] >= j - i).
   • Update dp[j] as the minimum of the current value dp[j] and dp[i] + 1 (which represents jumping from index i to j).
3. Result:
   • The answer will be dp[n-1], where n is the length of the array.

Time Complexity:

• Time Complexity: O(n²) where n is the length of the input array because for each index i, we may iterate over all possible reachable indices j.
• Space Complexity: O(n) for the dp array.

Optimized Approach:

An optimized greedy approach with O(n) time complexity is also possible, where we dynamically track the farthest index we can reach within the current jump range and increment the number of jumps accordingly.

---

Code in Various Languages:

1. C:

#include <stdio.h>
#include <limits.h>

int jump(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;

    int dp[numsSize];
    for (int i = 0; i < numsSize; i++) dp[i] = INT_MAX;
    dp[0] = 0;

    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j <= i + nums[i] && j < numsSize; j++) {
            if (dp[j] > dp[i] + 1) {
                dp[j] = dp[i] + 1;
            }
        }
    }
    return dp[numsSize - 1];
}

int main() {
    int nums[] = {2, 3, 1, 1, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", jump(nums, size));  // Output: 2
    return 0;
}

2. C++:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;

    vector<int> dp(n, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp[n - 1];
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << jump(nums) << endl;  // Output: 2
    return 0;
}

3. Java:

public class JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        JumpGameII solution = new JumpGameII();
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(solution.jump(nums));  // Output: 2
    }
}

4. Python:

def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0

    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(n):
        for j in range(i + 1, min(i + nums[i] + 1, n)):
            dp[j] = min(dp[j], dp[i] + 1)

    return dp[n - 1]

# Test the function
nums = [2, 3, 1, 1, 4]
print(jump(nums))  # Output: 2

5. C#:

using System;

public class JumpGameII {
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return 0;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = int.MaxValue;
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                dp[j] = Math.Min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

    public static void Main(string[] args) {
        JumpGameII solution = new JumpGameII();
        int[] nums = {2, 3, 1, 1, 4};
        Console.WriteLine(solution.Jump(nums));  // Output: 2
    }
}

6. JavaScript:

var jump = function(nums) {
    let n = nums.length;
    if (n <= 1) return 0;

    let dp = new Array(n).fill(Infinity);
    dp[0] = 0;

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j <= i + nums[i] && j < n; j++) {
            dp[j] = Math.min(dp[j], dp[i] + 1);
        }
    }
    return dp[n - 1];
};

// Test the function
const nums = [2, 3, 1, 1, 4];
console.log(jump(nums));  // Output: 2

---

Optimized Approach (Greedy Algorithm)

In this approach, instead of using a DP table, we can dynamically track the farthest we can reach in the current jump range, and count how many jumps we need to reach the end.

Optimized Approach – Greedy:

1. Initialization:
   • We keep track of:
     • jumps: the number of jumps made.
     • current_end: the farthest index we can reach with the current jump.
     • farthest: the farthest index we can reach with the next jump.
2. Iterate over the array and update farthest index for each step. If the current index reaches current_end, we make a jump and update current_end to farthest.
3. Exit when we reach the last index.

---

This approach runs in O(n) time, as we only pass through the array once.