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
ican jump to max indexi+nums[i] - alternatively, it can jump to all
i+kfor 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 alli+ks
- 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
ican jump to max indexi+nums[i] - we can keep a track of the
max_indexwe can jump to - as we iterate over the elements, if
i > max_index, this means that the indexiis 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
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Comments
Leave a Reply
This site uses Akismet to reduce spam. Learn how your comment data is processed.
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this