0055. Jump Game

Medium | Greedy + DP | 460 ms (91.12%), 15.2 MB (91.02%)

❓ Problem Statement

Source: LeetCode - Jump Game GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

The greedy method is more straightforward than the DP method. However, the mindsets for these two methods are the same.

Instead of checking from the beginning, we check whether we could reach the end backward. If the maximum jump could pass prevIndex, we assign the current position to prevIndex if curIndex + nums[i] >= prevIndex: prevIndex = curIndex.

In the end, we check whether prevIndex equals the starting index prevIndex == 0

🤖 Python3

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # (base case)
        if len(nums) == 1: return True
        if nums[0] == 0: return False
        
        # ==================================================
        #  Greedy                                          =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        prevIndex = len(nums) - 1
        for i in range(len(nums)-1, -1, -1):
            if i + nums[i] >= prevIndex: prevIndex = i
                
        return prevIndex == 0

        '''
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        dp = [False] * len(nums)
        dp[-1] = True
        
        cur = len(nums) - 1
        for i in range(len(nums)-2, -1, -1):
            if i + nums[i] >= cur:
                dp[i] = True
                cur = i
        
        return dp[0] == True
        '''

🤖 Java