Jump Game

Given an positive integer N and an array of N integers A[]. Each element in the array denotes the maximum length of jump you can cover. Find out if you can make it to the last index if you start at the first index of the list.

Paresh Krishna Sharma
3 min readMay 14, 2022

I guess most of us has been asked with this question (or with a little tweak) in in a coding round. Today we will try to solve this question with as easy method as I can explain.

First of all, we should get the understanding of the problem, and for that we should consider the figure below.

Source: GeeksforGeeks

We can see in figure that in array each index shows a number, which tells us that how many steps we can jump from that particular index. Let’s say on index 1, we have value 2; this means that we can jump two steps further from index 1 i.e. up-to index 1+2=3. And thus, following this calculation all around the array, we have to calculate that whether it is possible to reach at the end of the array or not.

Let’s code it…

For this, we have to take two variables, maxReach to calculate the maximum reachability from index i and current to keep the record of where we can reach maximum from the current index.

Now, we will iterate over the array to calculate the variables mentioned above. Firstly, we will calculate the maxReach by getting the maximum in between maxReach and the sum of index and max possible jump from that index (i + A[i]). As we have maxReach with us, now we will calculate that where we can reach maximum from the current index. For that, we will check whether current is equals to i, if yes then update the current with next maximum reachable index, i.e. maxReach.

After we have completed the iteration, we will have maximum reachable index in current. If this is greater than or equals to the last index of the array then we are successful and will return true otherwise false.

Complexity:

The overall time complexity for this method is O(N) because we have traversed the whole array once which is of length N. While space complexity for this would be O(1) because we have used two extra variables which will take constant space.

For full source code visit Github repository.

Thanks for reading.

--

--

Paresh Krishna Sharma

Unleashing the Power of Code, Data, and Creativity ✨ | Software Engineer at Microsoft | LinkedIn : www.linkedin.com/in/itsparesh