# Minimum number of jumps to reach end (O(n) solution) Part 2

Hello Everyone,

Another Approach:

1. For solving minimum jumps to reach the end of the array,
2. For every jump index, we consider needing to evaluate the corresponding step values in the index and using the index value divides the array into sub-parts and find out the maximum steps covered index.
3. The following code and explanation will give you a clear idea:
4. In each sub-array find out the max distance covered index as the first part of the array, and the second array

Input Array : {1, 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} → index position starts with 0

Steps :

Initial step is considering the first index and incrementing the jump

Jump = 1

1, { 3, 5, 9, 6, 2, 6, 7, 6, 8, 9} → 1 is considered as a first jump

next step

From the initial step, there is only one step to move so

Jump = 2

1,3, { 5, 9, 6,2, 6, 7, 6, 8, 9} → 1 is considered as a first jump

next step

Now we have the flexibility to choose any of {5,9,6} because the last step says we can move up to 3 steps

Consider it as a subarray, evaluate the max distance covers with each index position

As {5,9,6} index positions are {2,3,4}

so the total farther steps we can cover:

{7,12,10} → we can assume it as {7,12} & {10} are 2 sub-arrays where left part of arrays says max distance covered with 2 steps and right side array says max steps cover with remaining values

next step:

Considering the maximum distance covered in first array we iterate the remaining next elements

1,3,9 {6,2, 6, 7, 6, 8, 9}

From above step we already visited the 4th index we continue with next 5th index as explained above

{6,2, 6, 7, 6, 8, 9} index positions {4,5,6,7,8,9,10}

{10,7,12,14,14,17,19}

Max step covers here is 19 which corresponding index is 10

`// C++ program to illustrate Minimum`

`// number of jumps to reach end`

`#include <iostream>`

`using` `namespace` `std;`

`// Returns minimum number of jumps`

`// to reach arr[n-1] from arr`

`int` `minJumps(` `int` `arr[], ` `int` `n)`

`{`

` ` `// The number of jumps needed to`

` ` `// reach the starting index is 0`

` ` `if` `(n <= 1)`

` ` `return` `0;`

` ` `// Return -1 if not possible to jump`

` ` `if` `(arr == 0)`

` ` `return` `-1;`

` ` `// Stores the number of jumps`

` ` `// necessary to reach that maximal`

` ` `// reachable position.`

` ` `int` `jump = 1;`

` ` `// Stores the subarray last index`

` ` `int` `subArrEndIndex = arr;`

` ` `int` `i = 1;`

` ` `// Maximum steps covers in`

` ` `// first half of sub array`

` ` `int` `subArrFistHalfMaxSteps = 0;`

` ` `// Maximum steps covers`

` ` `// in second half of sub array`

` ` `int` `subArrSecondHalfMaxSteps = 0;`

` `

` ` `// Start traversing array`

` ` `for` `(i = 1; i < n;) {`

` ` `subArrEndIndex = i + subArrEndIndex;`

` `

` ` `// Check if we have reached`

` ` `// the end of the array`

` ` `if` `(subArrEndIndex >= n)`

` ` `return` `jump;`

` ` `int` `firstHalfMaxStepIndex = 0;`

` `

` ` `// Iterate the sub array`

` ` `// and find out the maxsteps`

` ` `// cover index`

` ` `for` `(; i < subArrEndIndex; i++) {`

` ` `int` `stepsCanCover = arr[i] + i;`

` ` `if` `(subArrFistHalfMaxSteps < stepsCanCover) {`

` ` `subArrFistHalfMaxSteps = stepsCanCover;`

` ` `subArrSecondHalfMaxSteps = 0;`

` ` `firstHalfMaxStepIndex = i;`

` ` `}`

` ` `else` `if` `(subArrSecondHalfMaxSteps`

` ` `< stepsCanCover) {`

` ` `subArrSecondHalfMaxSteps = stepsCanCover;`

` ` `}`

` ` `}`

` ` `if` `(i > subArrFistHalfMaxSteps)`

` ` `return` `-1;`

` ` `jump++;`

` `

` ` `// Next subarray end index`

` ` `// and so far calculated sub`

` ` `// array max step cover value`

` ` `subArrEndIndex = arr[firstHalfMaxStepIndex];`

` ` `subArrFistHalfMaxSteps = subArrSecondHalfMaxSteps;`

` ` `}`

` ` `return` `-1;`

`}`

`// Driver program to test above function`

`int` `main()`

`{`

` ` `int` `arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };`

` ` `int` `size = ` `sizeof` `(arr) / ` `sizeof` `(` `int` `);`

` ` `// Calling the minJumps function`

` ` `cout << (` `"Minimum number of jumps to reach end is %d "` `,`

` ` `minJumps(arr, size));`

` ` `return` `0;`

`}`

`// This code is contributed by praveen.kanike`

Output

3

Time complexity: O(n).

Auxiliary Space: O(1).