Jump Game II

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Approaches

1. Simple Approach (Dynamic Programming)

This approach uses dynamic programming to calculate the minimum number of jumps needed for each position.

Time Complexity: O(n^2), where n is the length of the array Space Complexity: O(n)

2. Optimal Approach (Greedy)

The optimal approach uses a greedy strategy to make the jump that allows reaching the farthest position.

Time Complexity: O(n) Space Complexity: O(1)

Solutions

Java Solution

// Simple Approach (Dynamic Programming)
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

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

        return dp[n - 1];
    }
}

// Optimal Approach (Greedy)
class Solution {
    public int jump(int[] nums) {
        int jumps = 0, currentJumpEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentJumpEnd) {
                jumps++;
                currentJumpEnd = farthest;
            }
        }
        return jumps;
    }
}

C++ Solution

// Simple Approach (Dynamic Programming)
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;

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

        return dp[n - 1];
    }
};

// Optimal Approach (Greedy)
class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, currentJumpEnd = 0, farthest = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            farthest = max(farthest, i + nums[i]);
            if (i == currentJumpEnd) {
                jumps++;
                currentJumpEnd = farthest;
            }
        }
        return jumps;
    }
};

Explanation

Simple Approach (Dynamic Programming)

Create a DP array where dp[i] represents the minimum number of jumps needed to reach index i.
Initialize dp[0] = 0 and all other elements to infinity.
For each position i, update the minimum jumps for all reachable positions from i.
The answer is in dp[n-1].

This approach is intuitive but may be inefficient for large inputs due to its quadratic time complexity.

Optimal Approach (Greedy)

This approach uses two pointers: one for the current jump's end and another for the farthest reachable position.

Initialize variables: jumps (number of jumps), currentJumpEnd (the farthest position that can be reached with the current number of jumps), and farthest (the overall farthest position that can be reached).
Iterate through the array:
- Update farthest if a farther position can be reached from the current index.
- If we've reached currentJumpEnd, we must make another jump:
  - Increment jumps.
  - Update currentJumpEnd to farthest.
Return jumps.

This method is efficient as it only requires a single pass through the array and has a linear time complexity.

Test Cases

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.
Input: nums = [2,3,0,1,4] Output: 2 Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [1,2,3] Output: 2 Explanation: Jump 1 step from index 0 to 1, then 2 steps to the last index.
Input: nums = [1,1,1,1] Output: 3 Explanation: Jump 1 step at a time to reach the last index.
Input: nums = [5,9,3,2,1,0,2,3,3,1,0,0] Output: 3 Explanation: Jump from index 0 to 1, then from 1 to 10, and finally to 11.

Jump Game