medium

Jump Game

To solve this problem using dynamic programming and greedy algorithms in JavaScript, we can follow these steps:

Dynamic Programming Approach:

• Create an array dp of length n, initialized with maximum possible values except for dp[0] = 0 since we start at index 0.
• Iterate through the array nums from left to right.
• For each index i, check if it is reachable from any previous index j (0 <= j < i) and update dp[i] with the minimum number of jumps required to reach index i.
• To update dp[i], compare the current value of dp[i] with dp[j] + 1 and take the minimum.
• Finally, return dp[n-1], which represents the minimum number of jumps required to reach the last index.

Here's the JavaScript code for the dynamic programming approach:

function minJumps(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
  dp[0] = 0;
 
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (j + nums[j] >= i) {
        dp[i] = Math.min(dp[i], dp[j] + 1);
      }
    }
  }
 
  return dp[n - 1];
}

The time complexity of this dynamic programming approach is O(n^2) since we have nested loops iterating through the array.

Greedy Approach:

• Initialize three variables: currJump to store the maximum reachable index from the current position, maxJump to store the maximum reachable index so far, and jumps to count the minimum number of jumps.
• Iterate through the array nums from left to right.
• For each index i, update maxJump by taking the maximum of maxJump and i + nums[i].
• If the current index i is equal to currJump, it means we have reached the maximum reachable index from the previous jump. So, update currJump with maxJump and increment jumps.
• Continue iterating until currJump reaches the last index.
• Finally, return jumps, which represents the minimum number of jumps required to reach the last index.

Here's the JavaScript code for the greedy approach:

function minJumps(nums) {
  const n = nums.length;
  let currJump = 0;
  let maxJump = 0;
  let jumps = 0;
 
  for (let i = 0; i < n - 1; i++) {
    maxJump = Math.max(maxJump, i + nums[i]);
    if (i === currJump) {
      currJump = maxJump;
      jumps++;
    }
  }
 
  return jumps;
}

The time complexity of this greedy approach is O(n) since we only iterate through the array once.

Both approaches provide a solution to find the minimum number of jumps required to reach the last index. The choice between using dynamic programming or a greedy approach depends on the specific requirements and constraints of the problem. In this case, the greedy approach offers a more efficient solution.