Minimum number of jumps (DSA)

Problem statement:(👈click here for GFG)

Given an array of N integers arr[] where each element represents the maximum length of the jump that can be made forward from that element. This means if arr[i] = x, then we can jump any distance y such that y ≤ x.

Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.

Note: Return -1 if you can't reach the end of the array.

Example 1:

Input:
N = 11 
arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 
Output: 3 
Explanation: 
First jump from 1st element to 2nd 
element with value 3. Now, from here 
we jump to 5th element with value 9, 
and from here we will jump to the last. 

Example 2:

Input :
N = 6
arr = {1, 4, 3, 2, 6, 7}
Output: 2 
Explanation: 
First we jump from the 1st to 2nd element 
and then jump to the last element.

Your task:
You don't need to read input or print anything. Your task is to complete function minJumps() which takes the array arr and it's size N as input parameters and returns the minimum number of jumps. If not possible return -1.

Expected Time Complexity: O(N)
Expected Space Complexity: O(1)

Constraints:
1 ≤ N ≤ 107
0 ≤ arri ≤ 10

solution: 

This problem can be solved using the greedy approach.

Algorithm:

• First, we check the base cases. If the size of the array is 0 or 1, then there is no need to jump and we can simply return 0.

• If the first element of the array is 0, then we cannot make any jump and we should return -1.

• We initialize the variable maxReach to the first element of the array, as this represents the maximum distance that we can jump from the first position.

• We initialize the variable step to the value of the first element of the array, as this represents the number of steps that we can take from the first position.

• We initialize the variable jump to 1, as we need at least one jump to reach the end of the array.

• We traverse the array from the second element to the last element.

• For each element, we update the maxReach to the maximum of its current value and the index of the element plus its value. This represents the maximum distance that we can jump from the current position.

• We decrement the step by 1, as we have taken one step from the previous position to the current position.

• If the step becomes 0, it means we have used all the steps that we could have taken from the previous position, and we need to take a jump to a new position. We increment the jump by 1.

• If at any point, step becomes 0 and the current position is greater than or equal to maxReach, it means we cannot make any jump further and we should return -1.

• If we reach the end of the array, we return the number of jumps that we have taken to reach the end.

function minJumps(arr, n) {

  if (n <= 1) {

    return 0;

  }

  if (arr[0] == 0) {

    return -1;

  }

  let maxReach = arr[0];

  let step = arr[0];

  let jump = 1;

  for (let i = 1; i < n; i++) {

    if (i === n - 1) {

      return jump;

    }

    maxReach = Math.max(maxReach, i + arr[i]);

    step--;

    if (step == 0) {

      jump++;

      if (i >= maxReach) {

        return -1;

      }

      step = maxReach - i;

    }

  }

  return -1;

}

Note: This code assumes that the input array has at least one element.

Thank you,

Learning is a never-ending process, and every day is an opportunity to learn something new. Keep exploring, keep pushing your limits, and keep striving towards your goals. Remember that every small step counts, and even the smallest progress is worth celebrating. Don't be afraid to ask questions, seek guidance, and learn from others. With dedication and hard work, you can achieve anything you set your mind to. So keep learning, keep growing, and keep shining!