You are given an array of integers and you are positioned at the first index. Every element represents maximum jump and you have to reach the last index with minimum jumps.
Example: Input: [2,3,1,1,4] Output: 2 Explanation: Jump from index 0 to index 1. Then jump 3 steps to reach last index.
Note:
Before solving this problem, please go through a similar problem. Jump Game.
A solution is a greedy approach; we need to go to the end of the list with the 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 the 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 equal 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
Solution in C++
#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; }
Output:
The minimum steps needed to reach the end = 2