Check if last index can be reached by jumping atmost jump[i] in each position

View Discussion

Improve Article

Save Article

Like Article

Given an array of jumps[] of length N, where each element denotes the maximum length of a jump forward from each index. The task is to find if it is possible to reach the last index.

Examples:

Input: arr[] = {2, 3, 1, 1, 4}
Output: True
Explanation: Possible ways to reach last index are:
(0->2->3->4), (0->2->3->1->1->4), (0->2->3->1->4) and (0->2->1->1->4).

Input:  arr[] = {3, 2, 1, 0, 4}
Output: False
Explanation: There is no way to reach last index.

Approach: The idea to solve the problem is as mentioned below:

We know that the last index is always reachable from itself. Assume that destination is jumping towards the first index. So the basic task is to check if the last possible index is reachable from the current index and update the last possible index accordingly.

Follow the below steps to solve the problems:

  • Maintain a variable LastAccuratePos (initialized to N-1) from which we can reach the last position.
  • Now start iterating the input array jumps[] from the right (second last position) to left.
    • In each iteration, calculate FurthestJump which is the summation of the index and the value at that index (i.e jumps[i]+i).
    • Check if FurthestJump is greater than or equal to LastAccuratePos. If yes, then we will update the value of LastAccuratePos with the current index.
  • After the iteration, check if LastAccuratePos is 0 then return True, else return False.

Below is the implementation of the above approach.

C++14

  

#include <bits/stdc++.h>

using namespace std;

  

bool isPossibleLastIndex(int* jumps, int& n)

{

    

    

    int LastAccuratePos = n - 1, FurthestJump = 0;

  

    for (int i = n - 2; i >= 0; i--) {

  

        

        FurthestJump = jumps[i] + i;

  

        

        

        

        if (FurthestJump >= LastAccuratePos)

            LastAccuratePos = i;

    }

  

    

    return LastAccuratePos == 0;

}

  

int main()

{

    int jumps[] = { 2, 3, 1, 1, 4 };

    int N = sizeof(jumps) / sizeof(jumps[0]);

  

    

    if (isPossibleLastIndex(jumps, N))

        cout << "True";

    else

        cout << "False";

  

    return 0;

}
Output

True

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

By Julio MarchiPosted on