Jump Game 4
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 + 1where:i + 1 < arr.length.i - 1where:i - 1 >= 0.jwhere:arr[i] == arr[j]andi != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Examples
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Similar Problems
[Jump Game 1 - Check if it reaches last index](jump-game-1-check-if-it-reaches-last-index) [Jump Game 2 - Get min jumps](jump-game-2-get-min-jumps) [Jump Game 3](jump-game-3) [Jump Game 5](jump-game-5) [Jump Game 6](jump-game-6) [Jump Game 7](jump-game-7) [Minimum jumps to reduce number to 1](minimum-jumps-to-reduce-number-to-1)
Solution
Method 1 – Breadth-First Search (BFS) 1
Intuition
The shortest path in an unweighted graph can be found using BFS. Here, each index is a node, and you can jump to adjacent indices or any index with the same value. BFS ensures we find the minimum steps to reach the last index.
Approach
- Build a map from each value in
arrto all indices where it appears. - Use a queue to perform BFS starting from index 0.
- At each step, consider:
- The next index (
i + 1) if within bounds and not visited. - The previous index (
i - 1) if within bounds and not visited. - All indices with the same value as the current index, skipping already visited ones.
- Mark visited indices to avoid cycles.
- Once all indices for a value are used, clear them from the map to prevent redundant processing.
- Return the number of steps when the last index is reached.
Code
C++
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n == 1) return 0;
unordered_map<int, vector<int>> m;
for (int i = 0; i < n; ++i) m[arr[i]].push_back(i);
queue<int> q;
vector<bool> vis(n, false);
q.push(0);
vis[0] = true;
int ans = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
int i = q.front(); q.pop();
if (i == n - 1) return ans;
vector<int>& nxt = m[arr[i]];
nxt.push_back(i - 1);
nxt.push_back(i + 1);
for (int j : nxt) {
if (j >= 0 && j < n && !vis[j]) {
vis[j] = true;
q.push(j);
}
}
m[arr[i]].clear();
}
++ans;
}
return -1;
}
}
Go
func minJumps(arr []int) int {
n := len(arr)
if n == 1 {
return 0
}
m := map[int][]int{}
for i, v := range arr {
m[v] = append(m[v], i)
}
vis := make([]bool, n)
q := []int{0}
vis[0] = true
ans := 0
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
idx := q[0]
q = q[1:]
if idx == n-1 {
return ans
}
for _, j := range append(append([]int{}, m[arr[idx]]...), idx-1, idx+1) {
if j >= 0 && j < n && !vis[j] {
vis[j] = true
q = append(q, j)
}
}
m[arr[idx]] = nil
}
ans++
}
return -1
}
Java
class Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n == 1) return 0;
Map<Integer, List<Integer>> m = new HashMap<>();
for (int i = 0; i < n; i++) m.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
Queue<Integer> q = new LinkedList<>();
boolean[] vis = new boolean[n];
q.offer(0);
vis[0] = true;
int ans = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int k = 0; k < sz; k++) {
int i = q.poll();
if (i == n - 1) return ans;
List<Integer> nxt = m.get(arr[i]);
nxt.add(i - 1);
nxt.add(i + 1);
for (int j : nxt) {
if (j >= 0 && j < n && !vis[j]) {
vis[j] = true;
q.offer(j);
}
}
nxt.clear();
}
ans++;
}
return -1;
}
}
Kotlin
class Solution {
fun minJumps(arr: IntArray): Int {
val n = arr.size
if (n == 1) return 0
val m = mutableMapOf<Int, MutableList<Int>>()
for (i in arr.indices) m.getOrPut(arr[i]) { mutableListOf() }.add(i)
val vis = BooleanArray(n)
val q: ArrayDeque<Int> = ArrayDeque()
q.add(0)
vis[0] = true
var ans = 0
while (q.isNotEmpty()) {
repeat(q.size) {
val i = q.removeFirst()
if (i == n - 1) return ans
val nxt = m[arr[i]]!!
nxt.add(i - 1)
nxt.add(i + 1)
for (j in nxt) {
if (j in 0 until n && !vis[j]) {
vis[j] = true
q.add(j)
}
}
nxt.clear()
}
ans++
}
return -1
}
}
Python
class Solution:
def minJumps(self, arr: list[int]) -> int:
n = len(arr)
if n == 1:
return 0
m: dict[int, list[int]] = {}
for i, v in enumerate(arr):
m.setdefault(v, []).append(i)
vis = [False] * n
q = [0]
vis[0] = True
ans = 0
while q:
nq = []
for i in q:
if i == n - 1:
return ans
for j in m[arr[i]] + [i - 1, i + 1]:
if 0 <= j < n and not vis[j]:
vis[j] = True
nq.append(j)
m[arr[i]].clear()
q = nq
ans += 1
return -1
Rust
impl Solution {
pub fn min_jumps(arr: Vec<i32>) -> i32 {
let n = arr.len();
if n == 1 { return 0; }
use std::collections::{HashMap, VecDeque};
let mut m: HashMap<i32, Vec<usize>> = HashMap::new();
for (i, &v) in arr.iter().enumerate() {
m.entry(v).or_default().push(i);
}
let mut vis = vec![false; n];
let mut q = VecDeque::new();
q.push_back(0);
vis[0] = true;
let mut ans = 0;
while !q.is_empty() {
for _ in 0..q.len() {
let i = q.pop_front().unwrap();
if i == n - 1 { return ans; }
let mut nxt = m.remove(&arr[i]).unwrap_or_default();
nxt.push(i.wrapping_sub(1));
nxt.push(i + 1);
for &j in &nxt {
if j < n && !vis[j] {
vis[j] = true;
q.push_back(j);
}
}
}
ans += 1;
}
-1
}
}
Complexity
- Time:
O(n)— Each index and value is processed at most once. - Space:
O(n)— For the map, queue, and visited array.