Jump Game III and IV — BFS with Queue

Some Jump Game variants are naturally BFS problems — you’re finding the shortest path in an implicit graph where nodes are array indices and edges are valid jumps.

Jump Game III (LeetCode 1306)

From index start, you can jump to i + arr[i] or i - arr[i]. Can you reach any index with value 0?

from collections import deque

def can_reach(arr, start):
    """
    BFS to check if any index with value 0 is reachable.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    queue = deque([start])
    visited = {start}

    while queue:
        i = queue.popleft()

        if arr[i] == 0:
            return True

        for next_i in [i + arr[i], i - arr[i]]:
            if 0 <= next_i < n and next_i not in visited:
                visited.add(next_i)
                queue.append(next_i)

    return False

Trace

arr = [4, 2, 3, 0, 3, 1, 2], start = 5

i=5, val=1: jump to 6, 4
i=6, val=2: jump to (8 invalid), 4 (visited via i=5? no, add)
i=4, val=3: jump to 7 (invalid), 1
i=1, val=2: jump to 3, (−1 invalid)
i=3, val=0: FOUND! → return True

Jump Game IV (LeetCode 1345)

Minimum jumps from index 0 to index n-1. From index i, you can:

1. Jump to i+1
2. Jump to i-1
3. Jump to any index j where arr[j] == arr[i] (same value teleport)

from collections import deque, defaultdict

def min_jumps(arr):
    """
    Minimum jumps to reach last index.
    Time: O(n), Space: O(n)
    """
    n = len(arr)
    if n == 1:
        return 0

    # Build same-value groups
    val_to_indices = defaultdict(list)
    for i, val in enumerate(arr):
        val_to_indices[val].append(i)

    queue = deque([(0, 0)])  # (index, jumps)
    visited = {0}

    while queue:
        i, jumps = queue.popleft()

        for next_i in [i-1, i+1] + val_to_indices.get(arr[i], []):
            if next_i == n - 1:
                return jumps + 1

            if 0 <= next_i < n and next_i not in visited:
                visited.add(next_i)
                queue.append((next_i, jumps + 1))

        # Clear group to avoid revisiting — critical optimization
        if arr[i] in val_to_indices:
            del val_to_indices[arr[i]]

    return -1

Why Delete the Group?

Without clearing val_to_indices[arr[i]] after processing, same-value groups cause O(n²) behavior. Consider [7,7,7,7,7,7,7,11] — without clearing, index 0 enqueues all 7s, index 1 tries to enqueue them again, etc.

After BFS processes any index with value 7, ALL indices with value 7 are already in the queue or visited. We’ll never need the group again.

Comparison

Edge Cases

• Single element — already at target, return 0
• All same values — one teleport jump reaches the end
• Alternating values — step through normally
• Large arrays with many duplicates — group clearing prevents TLE

When to Use BFS for Array Problems

Model the array as a graph when:

• Each index has multiple possible “next” indices
• You need the minimum number of steps/jumps
• The cost of each move is uniform (unweighted)

Related Problems

• Jump Game (LeetCode 55) — greedy, can you reach end?
• Jump Game II (LeetCode 45) — greedy, minimum jumps
• Minimum Genetic Mutation (LeetCode 433) — BFS on strings
• Open the Lock (LeetCode 752) — BFS on states