Jump Game

Introduction to the problem statement

You are given an array of non-negative integers, and you are initially positioned at the starting index of the array. Each element in the array represents the maximum jump length at that position.

Find whether you can reach the last index of the given array or not.

Example 1:

Input- jumps = [1, 2, 2, 1, 4]

Output- true

Explanation- We jump 1 step from index 0 to 1, then 2 steps from index 1 to 3, then 1 step to the last index

Example 2:

Input: jumps = [4, 3, 2, 1, 0, 4]

Output: false

Explanation: We will always arrive at index 4 no matter what. The maximum jump length from this index is 0, which makes it impossible to reach the end index.

Before moving to the approach of this problem, we recommend you to try this problem by yourself: Jump Game.

Approach - Forward iteration

In this approach, we will start with the first element of the array and move forward by one step each time. We also define a maxIndex variable that will keep track of the highest index we can reach from that particular index.

For example, We are at index 3, and the number at index 3 is 5, so the highest index we can reach from here is index 3 + 5 = 8.

So, we keep updating maxIndex with each iteration. In addition, we keep checking that the loop variable ‘i’ is always less than maxIndex. Otherwise, we are at an index out of our reach, i.e. we cannot reach the last element. So, if the variable ‘i’ exceeds maxIndex, we will exit from there.

To avoid these problems, we finally check whether ‘i’ is equal to the length of the array, which indicates that we have reached the end of the array.

Let’s understand the above approach with an example:

Input: jumps = [1, 5, 2, 1, 4]

1. i=0, maxIndex=1.
2. i=1, maxIndex=6.
3. i=2, maxIndex=6.
4. i=3, maxIndex=6.
5. i=4, maxIndex=8.

Now, i = 5 and length of the given array = 5

So, we can reach the last index.

Code in C++

#include<bits/stdc++.h>
using namespace std;

bool can_Reach_Last(vector<int>jumps) {
    int i = 0;
    int maxIndex = 0; // maximum index we can reach
    while (i < jumps.size() && i <= maxIndex) {
        maxIndex = max(i + jumps[i], maxIndex);
        i++;
    }
    if (i == jumps.size())  // we can reach the last index
        return true;
    return false;  //we can't reach the last index
}

int main()
{
    vector<int> a = {4, 3, 2, 1, 0, 4};
    if (can_Reach_Last(a))
        cout << "true" << endl;
    else
        cout << "false" << endl;
    return 0;
}

Output

false

Complexity Analysis

Time complexity- If n is the length of the given array, the time complexity of the solution is O(n).

Space complexity - The space complexity of the above solution is O(1).

Also see, Euclid GCD Algorithm