Given an array of jumps[] of size N, the place every aspect denotes the utmost size of a soar ahead from every index. The duty is to seek out whether it is potential to achieve the final index.
Examples:
Enter: arr[] = {2, 3, 1, 1, 4}
Output: True
Clarification: Potential methods to achieve final index are:
(0->2->3->4), (0->2->3->1->1->4), (0->2->3->1->4) and (0->2->1->1->4).Enter: Â arr[] = {3, 2, 1, 0, 4}
Output: False
Clarification: There is no such thing as a approach to attain final index.
Â
Method: The thought to resolve the issue is as talked about under:
We all know that the final index is all the time reachable from itself. Assume that vacation spot is leaping in the direction of the primary index. So the essential job is to test if the final potential index is reachable from the present index and replace the final potential index accordingly.
Comply with the under steps to resolve the issues:
- Keep a variable LastAccuratePos (initialized to N-1) from which we are able to attain the final place.
- Now begin iterating the enter array jumps[] from the correct (second final place) to left.
- In every iteration, calculate FurthestJump which is the summation of the index and the worth at that index (i.e jumps[i]+i).
- Examine if FurthestJump is bigger than or equal to LastAccuratePos. If sure, then we’ll replace the worth of LastAccuratePos with the present index.
- After the iteration, test if LastAccuratePos is 0 then return True, else return False.
Under is the implementation of the above strategy.
C++14
|
Time Complexity: O(N)
Auxiliary House: O(1)