# Jump Game | LeetCode | Solution Explained

55. Jump Game on LeetCode is a medium problem. I discuss the iterative dp solution as well as the greedy solutions. Problem link.

Contents

## Iterative DP

### Logic

• an index `i` can jump to max index `i+nums[i]`
• alternatively, it can jump to all `i+k` `for k in [1, nums[i]]`
• `for i in [0, n):`
• if we can’t reach `i`, we can just skip considering it
• if we can reach `i`, we can reach all `i+k`s
```class Solution:
def canJump(self, nums: List[int]) -&gt; bool:
n = len(nums)
dp = [False]*n
dp = True

for i in range(n):
if not dp[i]: continue #if False, we have no use for it
for k in range(1, nums[i]+1):
if i+k == n-1: return True
if i+k &lt;= n - 1: dp[i+k] = dp[i]

return dp[n-1]```
• Time: `O(N*K)`
• Space: `O(N)`

## O(1) Space Solution

### Logic

• an index `i` can jump to max index `i+nums[i]`
• we can keep a track of the `max_index` we can jump to
• as we iterate over the elements, if `i > max_index`, this means that the index `i` is unreachable
• so, any index after it is also unreachable – so, we return `False`
• else `max_index = max(max_index, i+nums[i])`
```class Solution:
def canJump(self, nums: List[int]) -&gt; bool:
max_index = 0
for i, x in enumeratenums):
# we have a gap, the current index cant be reached from the max_index reachable
if i &gt; max_index: return False
max_index = max(max_index, i+x)
return True```
• Time: `O(N)`
• Space: `O(1)`