# 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**hide

## 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

- if we can’t reach

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) dp = [False]*n dp[0] = 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 <= 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]) -> 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 > max_index: return False max_index = max(max_index, i+x) return True

- Time:
`O(N)`

- Space:
`O(1)`

## References

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.

Please write a Proof for this