Jump Game IV

Jump Game IV asks for the fewest jumps to reach the end of an array — and "fewest" is the word that should make you think BFS. Breadth-first search explores in waves, so the first wave that touches the goal is automatically the shortest path.

The slow way first

You could try every sequence of jumps with recursion, but the branching is enormous — each step can fan out to a whole group of equal values, so a naive search revisits the same indices again and again and blows up exponentially.

The question to ask: what is the fewest moves to a goal in an unweighted graph? That is the textbook job of BFS. Treat each index as a node, each legal jump as an edge, and expand level by level. The level at which the last index first appears is the answer.

The idea: BFS over an implicit graph

Each index i has three kinds of neighbors: i - 1, i + 1, and every index sharing its value. Precompute a map value -> [indices] so the same-value neighbors are instant.

The crucial trick: once you expand a value group, clear it. After the first index of value v is processed, every other v would re-scan the identical list — wasteful and quadratic. Emptying the group after first use means each value list is scanned at most once, keeping the whole search O(n).

Mark a node visited the moment you enqueue it, so it never enters the queue twice.

Walk through it

Step through the animation. We start at index 0 (value 7) and expand its wave. Its neighbors include the value-7 group [0, 5], so index 5 — the last index — is reached in a single jump. The instant a neighbor equals n - 1, BFS returns the current level.

Pseudocode

group equal values: same_val[value] = list of indices
visited = {0}; queue = [0]; steps = 0
while queue is not empty:
    for each node i in the current level:
        if i is the last index: return steps
        neighbors = same_val[arr[i]] + [i-1, i+1]
        clear same_val[arr[i]]            # use each value group once
        for each in-bounds, unvisited neighbor j:
            mark j visited and enqueue it
    steps += 1

The Python solution

def min_jumps(arr):
    same_val = defaultdict(list)
    for i, v in enumerate(arr):
        same_val[v].append(i)
    n = len(arr)
    visited = {0}
    queue = deque([0])
    steps = 0
    while queue:
        for _ in range(len(queue)):
            i = queue.popleft()
            if i == n - 1:
                return steps
            nbrs = same_val[arr[i]] + [i - 1, i + 1]
            same_val[arr[i]] = []
            for j in nbrs:
                if 0 <= j < n and j not in visited:
                    visited.add(j)
                    queue.append(j)
        steps += 1
    return 0

• same_val maps each value to the list of indices holding it — the same-value teleport edges.
• We seed BFS with index 0: visited = {0} and queue = [0], steps = 0.
• The for _ in range(len(queue)) loop drains exactly one level at a time, so steps counts BFS waves.
• Line 12 is the goal test: reaching n - 1 returns the current level immediately.
• nbrs combines the value group with the two array neighbors; line 15 clears the group right after, so no value list is ever scanned twice.
• Each neighbor is enqueued only if in bounds and not yet visited.

Complexity

Without clearing value groups the search degrades to O(n²) on inputs full of repeats. Clearing each group after first use is what guarantees the linear bound.

When this pattern shows up

Practice