As long as all indices (possibly except last index) have positive jumps, we can reach the end. Therefore, only way we may fail to reach the end is:
- Some index (before the end index) has 0 jump
- There isn’t an earlier index from which we could jump and skip over this zero-jump index.
Like the the case below:
We keep improving the maximum allowed index. If current index is beyond our reach, we cannot reach the last index.
Time: 
class Solution:
def canJump(self, nums: List[int]) -> bool:
# [2 3 1 1 4]
# 0 1 2 3 4
# 0 -> 2
# 1 -> 4
# 2 -> 4
# 3 -> 4
# 4 -> 8
# [3 2 1 0 4]
# 0 1 2 3 4
# 0 -> 3
# 1 -> 3
# 2 -> 3
# 3 -> 3 cannot move onto index 4
allowed_index = 0
for i, jump in enumerate(nums):
if i > allowed_index:
return False
allowed_index = max(allowed_index, i+jump)
return True
unreasonably effective 
Leave a comment