55. Jump Game

Description:

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

'''
[1] brute force(back tracking) - Time Limit Exceeded)

idea::
check all cases

code::
def jump(cur,dest):
    if cur>=dest:
        return True
    elif nums[cur]==0:
        return False
            
    check=False
    for i in range(1,nums[cur]+1):
        check|=jump(cur+i,dest)
                
    return check
        
return jump(0,len(nums)-1)

-T/C: O(max_jump^n)  # max_jump==10^5(constraints)
-S/C: O(n) # for function stack
'''

'''
[2] naive solution - bottom-up - accepted)

idea::
when denote pos[n] as possibility to reach at n th position (True or False)

ex1: [2,3,1,1,4]
pos[4]= (pos[3]&&nums[3]>=1) | (pos[2]&&nums[2]>=2) | (pos[1]&&nums[1]>=3) | (pos[0]&&nums[0]>=4)

simply, 
pos[0] is always True, because we start here.
from pos[0] to pos[nums[i]] are also True, because we cans jump there.

so, we can make pos list and check whether last index is reachable or not

code::
pos=[False for _ in range(len(nums))]
pos[0]=True

for i,val in enumerate(nums):
    if pos[i]:
        for jump in range(1,val+1):
            if i+jump>=len(nums)-1:
                return True
            pos[i+jump]=True
            
return False

-T/C: O(n*max_jump)
-S/C: O(n)
'''

'''
[3] greedy)

idea::
from last to first, check wheter i th step is reachable or not.

code::
dest=len(nums)-1  #destination
for i in range(0,len(nums)-1)[::-1]:
    if i+nums[i]>=dest:
        dest=i

return dest<=0

-T/C: O(n)
-S/C: O(1)

'''


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dest=len(nums)-1  #destination
        for i in range(0,len(nums)-1)[::-1]:
            if i+nums[i]>=dest:
                dest=i

        return dest<=0