Jump Game IV: BFS with Same-Value Jumps

You are given an integer array arr. From index i, you can jump to i - 1, i + 1, or any index j where arr[j] == arr[i]. Return the minimum number of jumps to reach the last index, starting from index 0. This is 1345. Jump Game IV, a hard problem that combines BFS with a hash map trick to avoid quadratic blowup.

Why BFS?

Every position in the array is a node. Every valid jump is an edge. All edges have the same cost (one jump), so this is an unweighted graph. BFS finds the shortest path in an unweighted graph, which makes it the right tool here.

The twist compared to a standard BFS on a grid is the "same-value" edges. Index 0 is not just connected to index 1. It is connected to every index that shares its value. That can be a lot of edges, and handling them naively leads to O(n^2) time. The key to this problem is managing those edges efficiently.

Building the graph: value-to-index map

Before running BFS, build a hash map from each value to the list of indices where it appears:

from collections import defaultdict
graph = defaultdict(list)
for i, val in enumerate(arr):
    graph[val].append(i)

For the example array [100, -23, -23, 404, 100, 23, 23, 23, 3, 404], the map looks like:

• 100 -> [0, 4]
• -23 -> [1, 2]
• 404 -> [3, 9]
• 23 -> [5, 6, 7]
• 3 -> [8]

When BFS reaches index i, you look up arr[i] in the map to find all same-value neighbors. Combined with i - 1 and i + 1, that gives you the full neighbor list.

The critical optimization

Here is the trap: if a value appears k times, the first time you process any index with that value, you iterate through all k indices. That is fine. But if you leave those indices in the map, the next time you process another index with the same value, you iterate through all k indices again, most of which are already visited. In the worst case (an array where every element is the same), this turns O(n) BFS into O(n^2).

The fix is simple. After you process all same-value neighbors for a given value, delete that key from the map. Every index in the list is either already visited or just got added to the queue, so you will never need the list again.

The solution

from collections import deque, defaultdict

def min_jumps(arr):
    n = len(arr)
    if n == 1:
        return 0

    # Build value -> indices map
    graph = defaultdict(list)
    for i, val in enumerate(arr):
        graph[val].append(i)

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

    while queue:
        jumps += 1
        for _ in range(len(queue)):
            idx = queue.popleft()

            # Check i-1, i+1, and same-value neighbors
            neighbors = []
            if idx - 1 >= 0:
                neighbors.append(idx - 1)
            if idx + 1 < n:
                neighbors.append(idx + 1)
            neighbors.extend(graph[arr[idx]])

            for next_idx in neighbors:
                if next_idx == n - 1:
                    return jumps
                if next_idx not in visited:
                    visited.add(next_idx)
                    queue.append(next_idx)

            # Delete the key so we never iterate this list again
            del graph[arr[idx]]

    return -1

Walking through it step by step

Let's trace BFS on arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404]. Blue cells are being processed, orange cells are newly discovered, green marks the goal.

Three jumps: 0 to 1 or 4 (level 1), then outward to 2, 3, 5 (level 2), and from 3 to 9 via the same-value link for 404 (level 3).

Why deleting processed values matters

Without the del graph[arr[idx]] line, consider an array like [7, 7, 7, 7, 7, 7, 7, 7, 11]. All indices 0 through 7 share value 7. When BFS processes index 0, it iterates through all 8 indices in graph[7] and adds 7 of them to the queue. When it later processes index 1 (already in the queue), it would iterate through all 8 indices again, finding them all visited. Then index 2 does the same, and index 3, and so on. That is 8 iterations times 8 indices = 64 operations for this one value group. Scale that to n elements all sharing the same value and you get O(n^2).

With the deletion, after processing index 0 and visiting all same-value neighbors, graph[7] is gone. When index 1 is processed, the lookup returns an empty list. Total work for the same-value group drops from O(n^2) to O(n).

Complexity analysis

Time: O(n). Building the hash map is O(n). Each index is added to the queue at most once and processed at most once. Each same-value group is iterated exactly once before deletion. The i - 1 and i + 1 checks are O(1) per index.

Space: O(n). The hash map stores all n indices (distributed across value groups). The visited set and queue each hold at most n entries.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently:

1. BFS shortest path on an implicit graph

The array is not literally a graph with an adjacency list. You build the neighbor relationships on the fly using i - 1, i + 1, and the hash map lookup. This pattern of treating array indices as graph nodes and running BFS for shortest path appears in many problems: word ladder, open the lock, sliding puzzle, and more.

visited = {start}
queue = deque([start])
steps = 0
while queue:
    steps += 1
    for _ in range(len(queue)):
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if neighbor == target:
                return steps
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

2. Value-to-index mapping with cleanup

Grouping array elements by value using a hash map, then consuming and deleting entries as you process them. This prevents redundant iteration and keeps the total work linear. You see the same idea in problems where you need to find all occurrences of a value quickly but only need to process each group once.

Edge cases

Before submitting, verify these:

• Single element [0]: you are already at the last index. Return 0.
• All same values [7, 7, 7, 7, 7]: from index 0, BFS discovers all indices in one level via the same-value jump. The last index is found immediately. Return 1 jump. The deletion ensures this runs in O(n), not O(n^2).
• Alternating values [1, 2, 1, 2, 1]: same-value groups are {1: [0,2,4], 2: [1,3]}. From 0, same-value jumps reach index 4 (the last index) in 1 jump.
• Two elements [1, 2]: one jump from index 0 to index 1 via i + 1. Return 1.
• Large array with unique values: every same-value group has size 1, so the same-value edges contribute nothing. BFS just walks forward one step at a time via i + 1.

From understanding to recall

The BFS template here is standard. The part that makes this problem hard is the same-value optimization: build the hash map, use it for neighbor lookup, then delete the key after processing. It is three lines of code, but forgetting any one of them means either wrong answers or TLE.

Under interview pressure, the deletion step is the one people miss. They write correct BFS, it works on small inputs, and then it times out on the large test case with repeated values. If you have drilled this pattern, the deletion is automatic. You see "same-value neighbors" and immediately think "iterate once, then delete."

Spaced repetition turns that insight into muscle memory. You write the BFS with the hash map from scratch, including the deletion line, at increasing intervals. After a few rounds, the full pattern is locked in.

Related posts

• Jump Game - The foundational greedy reachability problem
• Jump Game II - Minimum jumps with greedy BFS on contiguous ranges
• Number of Islands - Classic BFS/DFS on a grid graph