We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Jump Game IV

Difficulty: Hard

Problem Description

Given an array of integers arr, you are initially positioned at the first index of the array. In one step you can jump from index i to index i + 1, i - 1, or to any index j where arr[i] == arr[j] and i != j. Return the minimum number of steps to reach the last index of the array.

Key Insights

  • You can move to adjacent indices or jump to any index with the same value.
  • A breadth-first search (BFS) approach is suitable for finding the shortest path in an unweighted graph.
  • Tracking visited indices is crucial to avoid cycles and redundant work.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The problem can be solved using a breadth-first search (BFS) approach. We can treat the array as a graph where each index is a node. From each index, we can jump to adjacent indices or to any other index with the same value.

  1. Use a queue to explore nodes level by level, representing the number of jumps taken.
  2. Maintain a set or map to track visited indices to prevent reprocessing.
  3. For each index, enqueue its adjacent indices and all indices with the same value.
  4. Stop when the last index is reached, returning the number of jumps taken.

Code Solutions

from collections import deque, defaultdict

def minJumps(arr):
    if len(arr) <= 1:
        return 0
    
    # Build the graph with same-value indices
    graph = defaultdict(list)
    for i in range(len(arr)):
        graph[arr[i]].append(i)
    
    # BFS initialization
    queue = deque([0])
    visited = set([0])
    steps = 0
    
    while queue:
        for _ in range(len(queue)):
            index = queue.popleft()
            if index == len(arr) - 1:
                return steps
            
            # Check adjacent indices
            for neighbor in (index - 1, index + 1):
                if 0 <= neighbor < len(arr) and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
            
            # Check same-value indices
            same_value_indices = graph[arr[index]]
            for neighbor in same_value_indices:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
            # Clear the list to avoid redundant checks
            graph[arr[index]] = []
        
        steps += 1
    
    return -1  # Should not reach here
← Back to All Questions