LC 55 - Jump Game

Question

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.

Example 1:

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.

Example 2:

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.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Links

Question here and solution here

Solution

concept

memoization

Use DFS to go through each possible path and cache

bottom up dp

we iterate from the back, and as long as the cells can reach the end (or a pre-calculated cells that can reach the end).

greedy

This solution is to move the goal post (from the end) towards the left. We iterate from the back and if the i + nums[i] >= goal it means that this cell can reach the goal and hence we can move the goal post to i. Subsequent cells as long as they can reach the goal it is consider True.

code

class Solution:
	"""
	brute force DFS
	"""
    def canJump(self, nums: List[int]) -> bool:
        def dfs(i):
            if i == len(nums) - 1:
                return True
	        if nums[i] == 0:
				return False
                
            end = min(len(nums) - 1, i + nums[i])
            for j in range(i + 1, end + 1): # range func does not include end
                if dfs(j):
                    return True
            return False

        return dfs(0)
        
class Solution:
	"""
	dp: top down (memoization)
	TLE
	"""
    def canJump(self, nums: List[int]) -> bool:
        memo = {}

        def dfs(i):
            if i in memo:
                return memo[i]
            if i == len(nums) - 1:
                return True
            if nums[i] == 0:
                return False

            end = min(len(nums) - 1, i + nums[i])
            for j in range(i + 1, end + 1):
                if dfs(j):
                    memo[i] = True
                    return True
            memo[i] = False
            return False

        return dfs(0)
        
class Solution:
	"""
	another top down (memoization)
	similar to above
	TLE
	"""
    def canJump(self, nums: List[int]) -> bool:
        cache = {}
        def dfs(i):
            if i in cache:
                return cache[i]
            if i == len(nums) - 1:
                return True
            if nums[i] == 0:
                return False
            if i >= len(nums):
                return False
            
            for j in range(1, nums[i] + 1):
                if dfs(i + j):
                    cache[i] = True
                    return cache[i]
            cache[i] = False
            return cache[i]

        return dfs(0)
        
class Solution:
	"""
	dp: bottom up
	"""
    def canJump(self, nums: List[int]) -> bool:
        dp = [False]*len(nums)
        dp[-1] = True

        for i in range(len(nums)-2, -1, -1):
            end = min(len(nums) - 1, i + nums[i])
            for j in range(i + 1, end + 1):
                if dp[j]:
                    dp[i] = True
                    break

        return dp[0]
        
class Solution:
	"""
	greedy
	"""
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums)-1, -1, -1):
            if nums[i] + i >= goal:
                goal = i

        return True if goal == 0 else False

Complexity

time: $O(n^2)$ if DP, $O(n)$ if greedy
space: $O(n)$