Jump Game II in CPP

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [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.

Note:

You can assume that you can always reach the last index.

Before solving this problem, please go through a similar problem. Jump Game.

Given an array of non-negative integers determine if you are able to reach the last index in C++

The solution is a greedy approach; we need to go to end of the list with minimum jump.
Please follow the below explanation very carefully, as the solution is bit twisted, and is the maximum efficient solution.

If you have any other solution, please mention in the comment section, shall be updated in the article. [any efficiency will be ok]

So to solve this problem, we take 3 variables.

steps = number of steps covered
max_steps_can_be_reached = get the number of maximum steps can be reached for next step
steps_covered = how far we have already reached.

Initially all will be set to 0.

So the algorithm will work as below:

“steps_covered” will have number of steps it can travel. If there are no number of steps that can be reached, then update the “steps_covered” with the current value and increment the steps value.

If the value of “steps_covered” is greater than or equall to the size of the array, then we return the steps.

Note: The “max_steps_can_be_reached” will always hold the maximum steps that can be reached.

The code will look like shown below:

int jump( int a[], int n) 
{
  int steps = 0 ; // increment when we make a jump

  int steps_covered = 0 ; // it indicates the steps covered, if 

  int max_steps_can_be_reached = 0 ; // holds the max steps can be reached

  for ( int i = 0 ; i < n; ++ i) 
  {

    If (i > steps_covered) // if we run out of steps, update it
    {
      steps_covered = max_steps_can_be_reached;
      ++ steps;
    }

    max_steps_can_be_reached = max(max_steps_can_be_reached, i+ a[i]); // check if there is a value greater than present value.
  }

  Return steps;
}

We shall analyze with the help of example and a diagram.

[2,3,1,1,4] is the array.

Initially Pass 1:

steps = 0
max_steps_can_be_reached = 0
steps_covered = 0

for i = 0 to 4
  if( 0 > 0) false

  max_steps_can_be_reached = max(max_steps_can_be_reached, 0 + a[0]) => max(0, 2)

Pass 2:

steps = 0
max_steps_can_be_reached = 2
steps_covered = 0

for i = 1 to 4
  if( 1 > 0) true
    steps_covered = max_steps_can_be_reached
    steps++

  max_steps_can_be_reached = max(max_steps_can_be_reached, 1 + a[1]) => max(0, 4) => 4

Pass 3:

steps = 1
max_steps_can_be_reached = 4
steps_covered = 2

for i = 2 to 4
  if( 2 > 2) false

  max_steps_can_be_reached = max(max_steps_can_be_reached, 2 + a[2]) => max(4, 3) => 4

Pass 4:

steps = 1
max_steps_can_be_reached = 4
steps_covered = 2

for i = 3 to 4
  if( 3 > 2) true
    steps_covered = max_steps_can_be_reached
    steps++

  max_steps_can_be_reached = max(max_steps_can_be_reached, 3 + a[3]) => max(4, 4) => 4

Pass 5:

steps = 2
max_steps_can_be_reached = 4
steps_covered = 4

for i = 3 to 4
  if( 4 > 4) false
    

  max_steps_can_be_reached = max(max_steps_can_be_reached, 4 + a[4]) => max(4, 8) => 8

Exit loop.

Return steps. i.e 2

 

/*
* File     : jump_game_2.cpp
* Copyright: @ prodevelopertutorial.com
*/

#include<iostream>

using namespace std;
 
int jump(int A[], int n) 
{
    int ret = 0;
    int last = 0;
    int curr = 0;

    for (int i = 0; i < n; ++i) {
        if (i > last) {

            last = curr;
            ++ret;
        }
        curr = max(curr, i+A[i]);
    }

    return ret;
}

int main()
{
    int arr[] = {2, 3, 1, 1, 4};

    cout<<"The minimum steps needed to reach the end = "<< jump(arr, 5)<<endl;
}