Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction to the problem statement
2.
Approach - Forward iteration
2.1.
Code in C++
2.2.
Complexity Analysis
3.
Approach - Backward iteration
3.1.
Code in C++
3.2.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# 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

## Approach - Backward iteration

In this approach, we do the same thing as before, but we start from the end of the array and move backwards. If we can successfully reach the 0th index or the first element of the array from the last index, it means that we can also reach the last index from the first index of the array.

The variable minReach is defined as the array's final element. We update the minReach variable at each iteration by determining whether it is reachable from that index. If yes, the current index is replaced by the new minReach.

Now, we check whether the minReach is equal to 0, i.e. index of the first element. If yes, it means we can reach the last element.

### Code in C++

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

bool can_Reach_Last(vector<int> jumps) {
int minReach = jumps.size() - 1;
for (int i = jumps.size() - 2; i >= 0; i-- )
{
if (i + jumps[i] >= minReach)
minReach = i;
}
if (minReach == 0)
return true;
return false;
}

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

Output

``true``

### Complexity Analysis

Time complexity- It is O(n), where n is the length of the given array as we are running a for loop equal to the size of the array.

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

Check out this problem - First And Last Occurrences Of X

## Frequently asked questions

Q1. What is an array?

Ans:  An array is a collection of data elements that are similar and are stored in adjacent memory locations. It is the most basic data structure because each data element can be accessed directly using only its index number.

Q2. What is meant by dynamic programming?

Ans: Dynamic Programming (DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and taking advantage of the fact that the optimal solution to the overall problem depends on the optimal solution of the subproblems.

## Key Takeaways

So, this article discussed two approaches (forward iteration and backward iteration) to an exciting problem, Jump Game with example and its C++ code.

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free!

In case of any comments or suggestions, feel free to post them in the comments section.

Live masterclass