Solution to LeetCode 55 Jump Game & LeetCode 45 Jump Game II.
LeetCode 55
Jump Game (Medium) [link]
1] Greedy. This is how to determine if ‘Y’ is reachable: If there exists an ‘X’ that is reachable and it can jump to index X + nums[X] which is not less than ‘Y’, then index ‘Y’ is reachable. reach is used to keep the farthest position it can reach.
Time complexity O(n), space complexity O(1).
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
reach = 0
for i, n in enumerate(nums):
if i > reach: return False
reach = max(reach, i + n)
return True
2] Recursive DP with memoization
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
@cache
def dp(i):
if i >= n-1: return True
if i + nums[i] >= n-1: return True
for s in range(1,nums[i]+1):
if dp(i+s): return True
return False
return dp(0)
LeetCode 45
Jump Game II (Medium). [link]
1] Recursive DP.(TLE)
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
def dp(i):
if i >= n-1: return 0
if i + nums[i] >= n-1: return 1
ans = n
for s in range(1,nums[i]+1):
ans = min(ans, dp(i+s)+1)
return ans
return dp(0)
2] Greedy. Idea: every time choose the farthest position to start for the next jump.
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
maxReach, end, step = 0,0,0
for i in range(n-1): # avoid the final element
if maxReach >= i:
maxReach = max(maxReach, i + nums[i])
if i == end:
end = maxReach
step += 1
return step
