Jump Game

Problem Statement

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false otherwise.

Example 1:

Input: nums = [1,2,0,1,0]
Output: True

Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.

Example 2:

Input: nums = [1,2,1,0,1]
Output: False

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

You should aim for a solution with O(n) time and O(1) space, where n is the length of the input array.

Hint 1

Think about what it means to be able to reach the last index. Do we need to know how we reach it, or just that we can reach it?

Hint 2

Work backwards from the last index. For each index, check if you can reach the “goal” (initially the last index). If you can, then that index becomes the new “goal”.

Hint 3

If at the end, the goal is index 0, then you can reach the last index from index 0.

Solution

Recursion

def can_jump(nums: List[int]) -> bool:
def dfs(i: int) -> bool:
if i == len(nums) - 1:
return True
end = min(len(nums) - 1, i + nums[i])
for j in range(i + 1, end + 1):
if dfs(j):
return True
return False
return dfs(0)

Time complexity: O(n!) Space complexity: O(n)

Dynamic Programming (Top-Down)

def can_jump(nums: List[int]) -> bool:
memo = {}
def dfs(i: int) -> bool:
if i in memo:
return memo[i]
if i == len(nums) - 1:
return True
if nums[i] == 0:
return False
end = min(len(nums), i + nums[i] + 1)
for j in range(i + 1, end):
if dfs(j):
memo[i] = True
return True
memo[i] = False
return False
return dfs(0)

Time complexity: O(n ^ 2) Space complexity: O(n)

Dynamic Programming (Bottom-Up)

def can_jump(nums: List[int]) -> bool:
n = len(nums)
dp = [False] * n
dp[-1] = True
for i in range(n - 2, -1, -1):
end = min(n, i + nums[i] + 1)
for j in range(i + 1, end):
if dp[j]:
dp[i] = True
break
return dp[0]

Time complexity: O(n ^ 2) Space complexity: O(n)

Greedy

def can_jump(nums: List[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i
return goal == 0

Time complexity: O(n) Space complexity: O(1)