Python solution with detailed explanation


  • 0
    G

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

    Jump Game https://leetcode.com/problems/jump-game/?tab=Description

    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
    

Log in to reply
 

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