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

Constraints:

• 1 <= nums.length <= 10^4

• 0 <= nums[i] <= 10^5

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

💡 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

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean canJump(int[] nums) {
        /* base case */
        if(nums.length == 1) return true;
        if(nums[0] == 0) return false;
        
        boolean dp[] = new boolean[nums.length];
        dp[nums.length - 1]=true;
        
        int cur = nums.length - 1;
        for(int i=nums.length-2 ; i>=0 ; i--) {
            if(i + nums[i] >= cur){
                dp[i] = true;
                cur = i;
            }
        }
        
        return dp[0];
    }
}