MediumBlind75ArrayDPGreedy
Jump Game
You are given an integer array nums. You are initially positioned at the array's first index. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Examples
Input
nums = [2,3,1,1,4]
Output
true
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input
nums = [3,2,1,0,4]
Output
false
You will always arrive at index 3 that has value 0 and cannot jump further.
Constraints
- •
1 <= nums.length <= 10^4 - •
0 <= nums[i] <= 10^5
Approaches
Recursively try all possible jumps.
CodeT: O(2^n) | S: O(n)
def can_jump(nums):
def helper(i):
if i >= len(nums) - 1:
return True
for j in range(1, nums[i] + 1):
if helper(i + j):
return True
return False
return helper(0)Use DP to mark reachable indices.
CodeT: O(n^2) | S: O(n)
def can_jump(nums):
n = len(nums)
dp = [False] * n
dp[0] = True
for i in range(1, n):
for j in range(i):
if dp[j] and j + nums[j] >= i:
dp[i] = True
break
return dp[-1]Track the farthest reachable index.
Diagram
nums = [2,3,1,1,4]
i=0: farthest=max(0,2)=2
i=1: farthest=max(2,4)=4
i=2: farthest=max(4,3)=4
i=3: farthest=max(4,4)=4
4 >= 4 -> True
CodeT: O(n) | S: O(1)
def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False
farthest = max(farthest, i + nums[i])
return TrueComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) | Recursively try all possible jumps. |
| DP - Bottom Up | O(n^2) | O(n) | Use DP to mark reachable indices. |
| Greedy | O(n) | O(1) | Track the farthest reachable index. |
Recursion
T: O(2^n)S: O(n)
Recursively try all possible jumps.
DP - Bottom Up
T: O(n^2)S: O(n)
Use DP to mark reachable indices.
Greedy
T: O(n)S: O(1)
Track the farthest reachable index.
Common Mistakes
Using recursion without memoization
Not handling the case where the first element is 0
Using DP when greedy is more efficient