from collections import deque, defaultdict
class Solution:
def minJumps(self, arr):
if len(arr) == 1:
return 0
graph = defaultdict(list)
for idx, val in enumerate(arr):
graph[val].append(idx)
visited = [False] * len(arr)
visited[0] = True
queue = deque([(0, 0)]) # (index, steps)
while queue:
i, steps = queue.popleft()
# Check neighbors: i-1, i+1, all indices with arr[i]
for nei in [i - 1, i + 1]:
if 0 <= nei < len(arr) and not visited[nei]:
if nei == len(arr) - 1:
return steps + 1
visited[nei] = True
queue.append((nei, steps + 1))
for nei in graph[arr[i]]:
if not visited[nei]:
if nei == len(arr) - 1:
return steps + 1
visited[nei] = True
queue.append((nei, steps + 1))
# Prevent future redundant jumps for this value
graph[arr[i]].clear()
return -1
#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;
unordered_map<int, vector<int>> graph;
for (int i = 0; i < n; ++i) {
graph[arr[i]].push_back(i);
}
vector<bool> visited(n, false);
visited[0] = true;
queue<pair<int, int>> q;
q.push({0, 0});
while (!q.empty()) {
int i = q.front().first, steps = q.front().second;
q.pop();
for (int nei : {i - 1, i + 1}) {
if (nei >= 0 && nei < n && !visited[nei]) {
if (nei == n - 1) return steps + 1;
visited[nei] = true;
q.push({nei, steps + 1});
}
}
for (int nei : graph[arr[i]]) {
if (!visited[nei]) {
if (nei == n - 1) return steps + 1;
visited[nei] = true;
q.push({nei, steps + 1});
}
}
graph[arr[i]].clear();
}
return -1;
}
};
import java.util.*;
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n == 1) return 0;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
boolean[] visited = new boolean[n];
visited[0] = true;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int i = curr[0], steps = curr[1];
for (int nei : new int[]{i - 1, i + 1}) {
if (nei >= 0 && nei < n && !visited[nei]) {
if (nei == n - 1) return steps + 1;
visited[nei] = true;
queue.offer(new int[]{nei, steps + 1});
}
}
for (int nei : graph.get(arr[i])) {
if (!visited[nei]) {
if (nei == n - 1) return steps + 1;
visited[nei] = true;
queue.offer(new int[]{nei, steps + 1});
}
}
graph.get(arr[i]).clear();
}
return -1;
}
}
/**
* @param {number[]} arr
* @return {number}
*/
var minJumps = function(arr) {
if (arr.length === 1) return 0;
const graph = new Map();
for (let i = 0; i < arr.length; ++i) {
if (!graph.has(arr[i])) graph.set(arr[i], []);
graph.get(arr[i]).push(i);
}
const visited = new Array(arr.length).fill(false);
visited[0] = true;
const queue = [[0, 0]]; // [index, steps]
while (queue.length) {
const [i, steps] = queue.shift();
for (let nei of [i - 1, i + 1]) {
if (nei >= 0 && nei < arr.length && !visited[nei]) {
if (nei === arr.length - 1) return steps + 1;
visited[nei] = true;
queue.push([nei, steps + 1]);
}
}
for (let nei of graph.get(arr[i]) || []) {
if (!visited[nei]) {
if (nei === arr.length - 1) return steps + 1;
visited[nei] = true;
queue.push([nei, steps + 1]);
}
}
graph.set(arr[i], []);
}
return -1;
};
Given an array arr of integers, you are initially positioned at the first index. On each move, you can jump to:
i + 1) if it exists,i - 1) if it exists, orj where arr[i] == arr[j] and i != j.Your goal is to reach the last index of the array in the minimum number of jumps. It is guaranteed that at least one solution exists. You cannot revisit the same index in the same path. The function should return the minimum number of jumps required to reach the last index.
Constraints:
1 <= arr.length <= 5 * 10^4-10^9 <= arr[i] <= 10^9At first glance, the problem seems similar to the classic "Jump Game" but with a twist: you can also jump to any index with the same value. The brute-force approach would be to try all possible paths, but with the large input size, this would be too slow.
Instead, we notice that this is a shortest-path problem in a graph where each index is a node and edges exist between adjacent indices and all indices with the same value. This naturally leads us to use Breadth-First Search (BFS), which is optimal for finding the shortest path in an unweighted graph.
We also need to avoid revisiting indices, as cycles can occur through value-based jumps. To optimize further, once we have jumped via all indices with a certain value, we can "clear" or mark these as used to avoid redundant work in the future.
Here's a step-by-step breakdown of the approach:
arr.visited array or set to avoid revisiting indices.i-1, i+1, and all indices with the same value.This approach ensures that each index is visited at most once, and value-based jumps are not repeated unnecessarily.
Let's consider the input arr = [100, 23, 100, 100, 23, 100, 23].
100), steps = 0.
23), indices 2, 3, 5 (all 100).100), can jump to 4 (23) and 6 (23).
The minimum number of jumps is 2.
The algorithm is efficient and scalable for the input constraints.
The key insight is to model the problem as a shortest-path search in a graph, where BFS guarantees the minimum number of jumps. By using a hash map to efficiently find all possible value-based jumps and clearing them after use, we avoid redundant work. This leads to an elegant O(n) solution that is both simple and efficient for large arrays.