55. Jump Game
https://leetcode.com/problems/jump-game/
Intuition
We need to track if we can reach the last array index or not
Traverse L to R and track farthest index we can reach
farthest index = current index + max jump length at current index => i + nums[i]
If farthest index >= array length (0 offset) then we return true
During traversal if we come to a index beyond farthest possible so far, then we cannot travel any further and cannot reach end
for eg. 2 3 2 1 0 4 5
We cannot jump beyond 0, so there's no way to reach end of array
So check for if (i > furthest) > return false
Checking for nums[i] == 0 is not sufficient as previous element may allow us to bypass 0
for eg. 2 3 3 1 0 4 5
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.---
Intuition
We need to track if we can reach the last array index or not
Traverse L to R and track farthest index we can reach
farthest index = current index + max jump length at current index => i + nums[i]
If farthest index >= array length (0 offset) then we return true
During traversal if we come to a index beyond farthest possible so far, then we cannot travel any further and cannot reach end
for eg. 2 3 2 1 0 4 5
We cannot jump beyond 0, so there's no way to reach end of array
So check for if (i > furthest) > return false
Checking for nums[i] == 0 is not sufficient as previous element may allow us to bypass 0
for eg. 2 3 3 1 0 4 5
---
Time - O(n)
Space - O(1)
