Jump game iv

Array Hash Table Breadth-First Search

46.2% acceptance

Feb 25, 2026

3864

132

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 where: i + 1 < arr.length. i - 1 where: i - 1 >= 0. j where: arr[i] == arr[j] and i != 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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_jumps(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    if n == 1 { return 0; }
    let mut group: std::collections::HashMap<i32, Vec<usize>> = std::collections::HashMap::new();
    for (i, &v) in arr.iter().enumerate() {
      group.entry(v).or_default().push(i);
    }
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0usize);
    visited[0] = true;
    let mut steps = 0;
    while !queue.is_empty() {
      let sz = queue.len();
      for _ in 0..sz {
        let i = queue.pop_front().unwrap();
        if i == n - 1 { return steps; }
        // Jump ±1
        for &j in &[i.wrapping_sub(1), i + 1] {
          if j < n && !visited[j] {
            visited[j] = true;
            queue.push_back(j);
          }
        }
        // Jump to same value
        if let Some(v) = group.get(&arr[i]) {
          for &j in v {
            if !visited[j] {
              visited[j] = true;
              queue.push_back(j);
            }
          }
          group.remove(&arr[i]); // Avoid re-visiting
        }
      }
      steps += 1;
    }
    -1
  }
}