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
Recommended Time and Space Complexity
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)