Hello Everyone,

**Another Approach:**

- For solving minimum jumps to reach the end of the array,
- 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.
- The following code and explanation will give you a clear idea:
- 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[0]`

`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] == 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[0];`

` `

`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).