Member-only story
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.
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.
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.
