LeetCode 1345 - Jump Game IV

The problem is asking for the minimum number of steps required to reach the last index of an integer array, starting fro

leetcodehardarrayhash-tablebreadth-first-search

LeetCode Problem 1345

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Breadth-First Search

Solution

Problem Understanding

The problem is asking for the minimum number of steps required to reach the last index of an integer array, starting from the first index, given specific movement rules. You can move to the next index (i + 1), the previous index (i - 1), or any other index j where the value is equal to arr[i]. Essentially, you are navigating a graph where each index is a node, and edges exist between adjacent indices and indices with the same value.

The input, arr, is an array of integers of length up to 50,000, with values ranging from -10^8 to 10^8. The output is a single integer representing the minimum number of steps to reach the last index.

Constraints imply that a naive solution that examines every possible sequence of jumps would be too slow because the number of potential paths grows exponentially with the length of the array. Edge cases include arrays of length 1, arrays where all elements are the same, and arrays with widely spaced repeating values, which could cause unnecessary repeated jumps if not handled efficiently.

Approaches

The brute-force approach would involve recursively exploring all possible jumps from each index until the last index is reached. This guarantees correctness because it explores every path, but it is infeasible due to the exponential number of paths for arrays of size 50,000.

The key insight for a more efficient solution is to treat the array as an implicit graph where each index is a node connected to i+1, i-1, and all other indices with the same value. The problem then reduces to finding the shortest path in an unweighted graph, which is exactly what Breadth-First Search (BFS) is designed to do. To optimize further, after visiting all indices with a particular value, we can remove that value from the mapping to avoid unnecessary repeated work.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively explore all paths, too slow for large arrays
Optimal BFS O(n) O(n) Use BFS on graph where nodes are indices and edges are jumps, optimized by removing visited value groups

Algorithm Walkthrough

  1. Create a mapping from each value to all indices where it occurs. This allows O(1) access to all jumps of the same value.

  2. Initialize a queue for BFS with the starting index 0 and a visited set to avoid revisiting indices.

  3. Initialize a step counter to 0.

  4. While the queue is not empty:

  5. For each index at the current BFS level, check if it is the last index. If so, return the step count.

  6. Add neighbors i-1 and i+1 to the queue if they are within bounds and not visited.

  7. Add all other indices with the same value to the queue if they are not visited.

  8. Remove the current value from the mapping to avoid revisiting these indices later.

  9. Increment the step counter after processing each level.

  10. Continue until the last index is reached. The BFS guarantees that the first time the last index is reached, it is via the shortest path.

Why it works: BFS explores nodes level by level, guaranteeing that the first time a node is reached is via the shortest path from the start. By marking nodes as visited and removing processed value groups, we avoid cycles and redundant work.

Python Solution

from collections import deque, defaultdict
from typing import List

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return 0

        # Map each value to all indices where it occurs
        value_to_indices = defaultdict(list)
        for i, val in enumerate(arr):
            value_to_indices[val].append(i)

        queue = deque([0])
        visited = set([0])
        steps = 0

        while queue:
            for _ in range(len(queue)):
                current = queue.popleft()
                if current == len(arr) - 1:
                    return steps

                # Check neighbors
                neighbors = [current - 1, current + 1] + value_to_indices.get(arr[current], [])
                for neighbor in neighbors:
                    if 0 <= neighbor < len(arr) and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

                # Clear the list to prevent future redundant jumps
                value_to_indices[arr[current]] = []

            steps += 1

        return -1

The implementation first constructs the value-to-indices mapping for O(1) access to same-value jumps. BFS ensures that the first time the last index is reached, it is via the minimum steps. Clearing the mapping for each value after visiting avoids unnecessary future iterations.

Go Solution

package main

func minJumps(arr []int) int {
    n := len(arr)
    if n == 1 {
        return 0
    }

    valueToIndices := make(map[int][]int)
    for i, val := range arr {
        valueToIndices[val] = append(valueToIndices[val], i)
    }

    queue := []int{0}
    visited := make([]bool, n)
    visited[0] = true
    steps := 0

    for len(queue) > 0 {
        nextQueue := []int{}
        for _, current := range queue {
            if current == n-1 {
                return steps
            }

            neighbors := []int{current - 1, current + 1}
            neighbors = append(neighbors, valueToIndices[arr[current]]...)

            for _, neighbor := range neighbors {
                if neighbor >= 0 && neighbor < n && !visited[neighbor] {
                    visited[neighbor] = true
                    nextQueue = append(nextQueue, neighbor)
                }
            }

            valueToIndices[arr[current]] = nil
        }
        queue = nextQueue
        steps++
    }

    return -1
}

In Go, a slice is used as the BFS queue, and a boolean slice tracks visited indices. Clearing the slice in the map prevents redundant jumps, similar to the Python solution.

Worked Examples

Example 1: arr = [100,-23,-23,404,100,23,23,23,3,404]

Level 0: [0] → steps = 0

Level 1: [1, 4] → jump from 0 to 1 or 4

Level 2: [2, 3, 5] → from 4 jump to 3

Level 3: [9] → from 3 jump to 9, last index reached

Example 2: arr = [7]

Level 0: [0] → start is last index → steps = 0

Example 3: arr = [7,6,9,6,9,6,9,7]

Level 0: [0] → steps = 0

Level 1: [7] → jump directly to last index using value 7 → steps = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most once and each value group is processed once
Space O(n) Storage for queue, visited set, and value-to-indices map

The BFS ensures that we visit each index exactly once, and by clearing the mapping after processing a value, we avoid redundant visits for same-value jumps.

Test Cases

# Provided examples
assert Solution().minJumps([100,-23,-23,404,100,23,23,23,3,404]) == 3  # multiple jumps
assert Solution().minJumps([7]) == 0  # single element
assert Solution().minJumps([7,6,9,6,9,6,9,7]) == 1  # jump using value

# Boundary values
assert Solution().minJumps([1,2]) == 1  # small array
assert Solution().minJumps([1,1,1,1,1]) == 1  # all elements same
assert Solution().minJumps(list(range(100))) == 99  # strictly increasing, no same values

# Stress cases
arr = [1] + [2]*1000 + [1]  # long array with repeated middle elements
assert Solution().minJumps(arr) == 2  # jump from 0 -> last 1 directly using value
Test Why
Multiple jumps Validates BFS finds minimum steps across mixed jumps
Single element Edge case, start is already the end
Jump using value Ensures same-value jumps are utilized efficiently
Small array Basic correctness on minimal input
All elements same Avoids redundant jumps, ensures optimal path
Strictly increasing No same-value jumps, tests linear BFS
Long repeated elements Tests performance and correctness with large input

Edge Cases

Single element array: If the array has only one element, the minimum steps is 0. BFS handles this automatically by checking the start index.

All elements are the same: If the array consists of identical values, the naive BFS could repeatedly jump between the same-value indices. Clearing the mapping after first use ensures we only consider these jumps once.

Large array with distant duplicates: For arrays with repeating values that are far apart, it is important not to revisit already processed