Jump Game I and II
Determine reachability and minimum jumps using a greedy range-expansion approach that avoids the need for DP.
Jump Game I: Can You Reach the End?
Jump Game I (LeetCode 55): given an array where nums[i] is the maximum jump length from index i, determine if you can reach the last index starting from index 0. For [2, 3, 1, 1, 4], you can reach the end (jump 2→3, then 3 gets you to end). For [3, 2, 1, 0, 4], you cannot (always land on 0, which has a jump of 0). A greedy solution runs in O(n).
# Can you reach the last index?
nums1 = [2, 3, 1, 1, 4] # True: 0→1→4 or 0→2→3→4
nums2 = [3, 2, 1, 0, 4] # False: always land on index 3 (value 0)
# At index 3 (value 0): no matter how you get here,
# you can't jump further to reach index 4
print('nums1 last index:', len(nums1)-1)
print('nums2 index 3 jump value:', nums2[3]) # 0 = stuckGreedy: Track Maximum Reach
The greedy insight for Jump Game I: maintain max_reach, the farthest index reachable so far. At each index i, update max_reach = max(max_reach, i + nums[i]). If at any point i > max_reach, the current index is unreachable — return False. If we reach or pass the last index, return True. No DP or backtracking needed.
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: # can't reach index i
return False
max_reach = max(max_reach, i + jump)
if max_reach >= len(nums) - 1:
return True # early exit
return True
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
print(can_jump([0])) # True (already at last index)
print(can_jump([1, 0, 0])) # False