Jump Game I e II

Jump Game I: è possibile raggiungere la fine

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

Greedy: tenere traccia della portata massima

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

Tracciare Jump Game I

def can_jump_trace(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        print(f'i={i}, jump={jump}, max_reach before={max_reach}', end='')
        if i > max_reach:
            print(' → UNREACHABLE')
            return False
        max_reach = max(max_reach, i + jump)
        print(f' → max_reach={max_reach}')
    return True

print('Result:', can_jump_trace([3, 2, 1, 0, 4]))

Jump Game II: numero minimo di salti

def jump(nums):
    n = len(nums)
    if n == 1: return 0  # already at destination
    jumps = 0
    curr_end = 0   # end of current jump's range
    farthest = 0   # farthest reachable in next jump
    for i in range(n - 1):  # don't jump from last index
        farthest = max(farthest, i + nums[i])
        if i == curr_end:    # exhausted current jump range
            jumps += 1
            curr_end = farthest
            if curr_end >= n - 1: break
    return jumps

print(jump([2, 3, 1, 1, 4]))  # 2 (0→1→4)
print(jump([2, 3, 0, 1, 4]))  # 2 (0→1→4)
print(jump([1, 2, 1, 1, 1])) # 3

Visualizzare Jump Game II

def jump_traced(nums):
    n = len(nums)
    jumps = curr_end = farthest = 0
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        print(f'i={i}: farthest={farthest}, curr_end={curr_end}')
        if i == curr_end:
            jumps += 1
            curr_end = farthest
            print(f'  → JUMP #{jumps}, new range ends at {curr_end}')
            if curr_end >= n - 1: break
    return jumps

print('Min jumps:', jump_traced([2, 3, 1, 1, 4]))

Perché la strategia greedy è corretta per Jump II

# Correctness verification: compare to BFS
from collections import deque

def jump_bfs(nums):
    n = len(nums)
    if n == 1: return 0
    visited = [False] * n
    visited[0] = True
    queue = deque([0])
    level = 0
    while queue:
        level += 1
        for _ in range(len(queue)):
            pos = queue.popleft()
            for j in range(1, nums[pos] + 1):
                nxt = pos + j
                if nxt >= n - 1: return level
                if not visited[nxt]:
                    visited[nxt] = True
                    queue.append(nxt)
    return -1

# Both should give same results
for nums in [[2,3,1,1,4],[2,3,0,1,4],[1,2,1,1,1]]:
    print(jump(nums), '==', jump_bfs(nums))

Alternativa con programmazione dinamica per Jump Game II

def jump_dp(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    for j in range(n):
        for k in range(1, nums[j] + 1):
            if j + k < n:
                dp[j+k] = min(dp[j+k], dp[j] + 1)
    return dp[n-1]

print(jump_dp([2, 3, 1, 1, 4]))  # 2
print(jump_dp([1, 2, 1, 1, 1]))  # 3

# Greedy is O(n), DP is O(n * max_jump)
# For large inputs with big jump values, greedy is much faster

Jump Game III: raggiungere l'indice zero

from collections import deque

def can_reach(arr, start):
    n = len(arr)
    visited = set()
    queue = deque([start])
    while queue:
        idx = queue.popleft()
        if arr[idx] == 0: return True
        if idx in visited: continue
        visited.add(idx)
        for nxt in [idx + arr[idx], idx - arr[idx]]:
            if 0 <= nxt < n and nxt not in visited:
                queue.append(nxt)
    return False

print(can_reach([4,2,3,0,3,1,2], 5))  # True (5→4→1→3, arr[3]=0)
print(can_reach([3,0,2,1,2], 2))      # False (can't reach index 1, arr[1]=0)

Jump Game VII: raggiungibilità con un intervallo

def can_reach_vii(s, min_jump, max_jump):
    n = len(s)
    reach = [False] * n
    reach[0] = True
    pre = [0] * (n + 1)  # prefix sum of reachable positions
    pre[1] = 1
    for j in range(1, n):
        # Window sum: any reachable position in [j-maxJump, j-minJump]?
        lo = max(0, j - max_jump)
        hi = max(0, j - min_jump + 1)
        window_sum = pre[hi] - pre[lo]
        if s[j] == '0' and window_sum > 0:
            reach[j] = True
        pre[j+1] = pre[j] + (1 if reach[j] else 0)
    return reach[n-1]

print(can_reach_vii('011010', 2, 3))  # True
print(can_reach_vii('01101110', 2, 3))  # False

Confronto tra le soluzioni greedy e BFS

# Both approaches are O(n) time
# Greedy: O(1) space — preferred in interviews
# BFS: O(n) space — easier to derive

# Greedy advantage: no auxiliary data structures
def jump_greedy(nums):
    n, jumps, curr, far = len(nums), 0, 0, 0
    for i in range(n-1):
        far = max(far, i+nums[i])
        if i == curr: jumps += 1; curr = far
    return jumps

# BFS equivalence: each level = one jump
from collections import deque
def jump_bfs(nums):
    n = len(nums)
    if n == 1: return 0
    q, visited, level = deque([0]), {0}, 0
    while q:
        level += 1
        for _ in range(len(q)):
            pos = q.popleft()
            for j in range(1, nums[pos]+1):
                nxt = pos + j
                if nxt >= n-1: return level
                if nxt not in visited: visited.add(nxt); q.append(nxt)
    return -1

nums = [2,3,1,1,4]
print(jump_greedy(nums), '==', jump_bfs(nums))  # both 2

Riepilogo della complessità di Jump Game

# Comparison: all versions on the same input
nums = [2, 3, 1, 1, 4]

# Jump I
def can_jump(nums):
    mr = 0
    for i, j in enumerate(nums):
        if i > mr: return False
        mr = max(mr, i+j)
    return True

# Jump II greedy O(n) O(1)
def jump_min(nums):
    n, jumps, curr, far = len(nums), 0, 0, 0
    for i in range(n-1):
        far = max(far, i+nums[i])
        if i == curr:
            jumps += 1; curr = far
            if curr >= n-1: break
    return jumps

print('Can reach:', can_jump(nums))    # True
print('Min jumps:', jump_min(nums))    # 2
print('Complexity: O(n) time, O(1) space')

Verifica rapida

Riepilogo della lezione