# Python solution with detailed explanation

• Solution with discussionhttps://discuss.leetcode.com/topic/80174/python-solution-with-detailed-explanation

Memoization Solution

• Draw the recursion tree. Notice we can have stack overflow for an exremely large input. MLE
``````class Solution(object):
def canJump(self, nums):
return self.can_jump_memoization(0, nums, {})

def can_jump_memoization(self, i, array, cache):
"""
:type nums: List[int]
:rtype: bool
"""
if i >= len(array):
return False
elif i == len(array)-1:
return True
elif i in cache:
return cache[i]
else:
cache[i] = False
for j in range(1, array[i]+1):
if self.can_jump_memoization(j+i, array, cache):
cache[i] = True
return True
return cache[i]
``````

Dynamic Programming Solution

• Complexity is order n^2. We have an issue here - TLE.
``````class Solution(object):
def canJump(self, nums):
dp = [False]*len(nums)
dp[0] = True
for i in range(1,len(nums)):
for j in range(i-1,-1,-1):
if dp[j] == True and nums[j] + j >= i:
dp[i] = True
break
return dp[-1]
``````

Linear - Ladders and Stairs Solution

• Linear complexity
``````class Solution(object):
def canJump(self, nums):
max_reach = nums[0]
end_index = len(nums)-1
if max_reach >= end_index:
return True
for i in range(1, len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i+nums[i])
if max_reach >= end_index:
return True
return False
``````
``````class Solution(object):
def canJump(self, nums):
max_reach, i, N = 0, 0, len(nums)
while i < N and max_reach >= i:
max_reach = max(max_reach, i+nums[i])
if max_reach >= N-1:
return True
i += 1
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.