1345. Jump Game IV

/**
 * Problem: LeetCode 1345 - Jump Game IV
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        // Map each unique number to the list of its indices
        Map<Integer, List<Integer>> valueIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valueIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }

        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n];

        queue.offer(0);
        visited[0] = true;
        int steps = 0;

        // Level-order BFS for shortest path
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int k = 0; k < size; k++) {
                int curr = queue.poll();

                // Target reached: last index of array
                if (curr == n - 1) {
                    return steps;
                }

                // Transition 1: jump backward (curr - 1)
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    queue.offer(curr - 1);
                }

                // Transition 2: jump forward (curr + 1)
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    queue.offer(curr + 1);
                }

                // Transition 3: jump to any same-value index
                List<Integer> sameValIndices = valueIndices.get(arr[curr]);
                if (sameValIndices != null) {
                    for (int nextIdx : sameValIndices) {
                        if (!visited[nextIdx]) {
                            visited[nextIdx] = true;
                            queue.offer(nextIdx);
                        }
                    }
                    // Crucial optimization: clear the list to avoid O(N^2) redundant expansions
                    valueIndices.remove(arr[curr]);
                }
            }

            steps++;
        }

        return steps;
    }
}

"""
Problem: LeetCode 1345 - Jump Game IV
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from collections import defaultdict, deque
from typing import List

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n <= 1:
            return 0
        
        # Group indices by element value
        value_indices = defaultdict(list)
        for i, val in enumerate(arr):
            value_indices[val].append(i)
            
        queue = deque([0])
        visited = [False] * n
        visited[0] = True
        steps = 0
        
        # Level-order Breadth-First Search
        while queue:
            for _ in range(len(queue)):
                curr = queue.popleft()
                
                # Reached the last index
                if curr == n - 1:
                    return steps
                
                # Option 1: Jump backward
                if curr - 1 >= 0 and not visited[curr - 1]:
                    visited[curr - 1] = True
                    queue.append(curr - 1)
                    
                # Option 2: Jump forward
                if curr + 1 < n and not visited[curr + 1]:
                    visited[curr + 1] = True
                    queue.append(curr + 1)
                    
                # Option 3: Jump to same value indices
                if arr[curr] in value_indices:
                    for next_idx in value_indices[arr[curr]]:
                        if not visited[next_idx]:
                            visited[next_idx] = True
                            queue.append(next_idx)
                    # Erase from map to prevent redundant O(N^2) searches
                    del value_indices[arr[curr]]
                    
            steps += 1
            
        return steps

/**
 * Problem: LeetCode 1345 - Jump Game IV
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1) {
            return 0;
        }

        // Group indices with the same value
        unordered_map<int, vector<int>> valueIndices;
        for (int i = 0; i < n; ++i) {
            valueIndices[arr[i]].push_back(i);
        }

        queue<int> q;
        vector<bool> visited(n, false);

        q.push(0);
        visited[0] = true;
        int steps = 0;

        // Standard level-order BFS for shortest unweighted path
        while (!q.empty()) {
            int sz = q.size();

            for (int k = 0; k < sz; ++k) {
                int curr = q.front();
                q.pop();

                // Target reached
                if (curr == n - 1) {
                    return steps;
                }

                // Transition 1: jump backward (curr - 1)
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    q.push(curr - 1);
                }

                // Transition 2: jump forward (curr + 1)
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    q.push(curr + 1);
                }

                // Transition 3: jump to any same-value index
                auto it = valueIndices.find(arr[curr]);
                if (it != valueIndices.end()) {
                    for (int nextIdx : it->second) {
                        if (!visited[nextIdx]) {
                            visited[nextIdx] = true;
                            q.push(nextIdx);
                        }
                    }
                    // Prune same-value list to prevent quadratic traversal
                    valueIndices.erase(it);
                }
            }

            steps++;
        }

        return steps;
    }
};

/**
 * Problem: LeetCode 1345 - Jump Game IV
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} arr
 * @return {number}
 */
var minJumps = function(arr) {
    const n = arr.length;
    if (n <= 1) return 0;

    // Map each value to a list of its indices
    const valueIndices = new Map();
    for (let i = 0; i < n; i++) {
        if (!valueIndices.has(arr[i])) {
            valueIndices.set(arr[i], []);
        }
        valueIndices.get(arr[i]).push(i);
    }

    const queue = [0];
    let head = 0;
    const visited = new Uint8Array(n);
    visited[0] = 1;
    let steps = 0;

    // Breadth-First Search level by level
    while (head < queue.length) {
        const levelSize = queue.length - head;

        for (let k = 0; k < levelSize; k++) {
            const curr = queue[head++];

            // Target reached
            if (curr === n - 1) {
                return steps;
            }

            // Transition 1: jump backward (curr - 1)
            if (curr - 1 >= 0 && !visited[curr - 1]) {
                visited[curr - 1] = 1;
                queue.push(curr - 1);
            }

            // Transition 2: jump forward (curr + 1)
            if (curr + 1 < n && !visited[curr + 1]) {
                visited[curr + 1] = 1;
                queue.push(curr + 1);
            }

            // Transition 3: jump to same-value indices
            if (valueIndices.has(arr[curr])) {
                const sameValIndices = valueIndices.get(arr[curr]);
                for (let i = 0; i < sameValIndices.length; i++) {
                    const nextIdx = sameValIndices[i];
                    if (!visited[nextIdx]) {
                        visited[nextIdx] = 1;
                        queue.push(nextIdx);
                    }
                }
                // Crucial optimization: delete to prevent redundant O(N^2) edge visits
                valueIndices.delete(arr[curr]);
            }
        }

        steps++;
    }

    return steps;
};