LeetCode Solutions Blog

Jump Game IV

Number: 1447

Difficulty: Hard

Paid? No

Problem Description

Given an array of integers, you start at the first index and want to reach the last index with the minimum number of jumps. From an index i, you can move to i+1, i-1 (if within bounds), or any index j (where i != j) such that arr[i] == arr[j].

Key Insights

The problem can be modeled as a graph where each index is a node.
Adjacent nodes (i-1, i+1) and nodes with the same value are connected by an edge.
A Breadth-First Search (BFS) can be used to find the shortest path.
To prevent redundant work, once you use all connections for a specific value, remove them from further consideration.
Use a hash table (dictionary) to map each value to its list of indices.

Space and Time Complexity

Time Complexity: O(n) on average, in worst-case O(n^2) if many duplicate values exist. Space Complexity: O(n), to store the mapping and the queue used in BFS.

Solution

We solve the problem using BFS, which is well-suited for finding the shortest path in an unweighted graph. First, we create a dictionary that groups indices by their values. We then start the BFS from the first index. At each step, we try to move to three kinds of neighbors: i-1, i+1, and all j where arr[j] equals the current value. After processing all same-value neighbors, we clear the list for that value to avoid redundant traversals. This prevents cycles and ensures the algorithm remains efficient.

Code Solutions

# Python Solution with detailed line-by-line comments

from collections import deque, defaultdict

def minJumps(arr):
    # If the array has only one element, no jump is needed.
    if len(arr) == 1:
        return 0

    # Build a mapping from each value to all indices that have that value.
    indices_map = defaultdict(list)
    for index, value in enumerate(arr):
        indices_map[value].append(index)
    
    # Initialize a BFS queue; each element is a tuple (current_index, jump_count)
    queue = deque([(0, 0)])
    
    # Set to track visited indices so we don't process the same index twice.
    visited = {0}
    
    while queue:
        current_index, jumps = queue.popleft()
        
        # Check if we have reached the last index
        if current_index == len(arr) - 1:
            return jumps
        
        # Explore neighbors: same value indices, next index and previous index
        # Same value indices: retrieve from mapping
        same_value_indices = indices_map[arr[current_index]]
        # Iterate over same value indices
        for neighbor_index in same_value_indices:
            if neighbor_index not in visited:
                visited.add(neighbor_index)
                queue.append((neighbor_index, jumps + 1))
        # Clear list to prevent repetitive processing in future
        indices_map[arr[current_index]].clear()
        
        # Check neighbor: current_index + 1 if within bounds
        if current_index + 1 < len(arr) and current_index + 1 not in visited:
            visited.add(current_index + 1)
            queue.append((current_index + 1, jumps + 1))
        
        # Check neighbor: current_index - 1 if within bounds
        if current_index - 1 >= 0 and current_index - 1 not in visited:
            visited.add(current_index - 1)
            queue.append((current_index - 1, jumps + 1))
    
    return -1  # This return would never be reached because the problem guarantees a solution.

# Example usage:
# print(minJumps([100,-23,-23,404,100,23,23,23,3,404]))