Jump Game 4

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 + 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.

Examples

Example 1:

1
2
3


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:

1
2
3


Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.

Example 3:

1
2
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.

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 arr to 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


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
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


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.

Problem#

Examples#

Similar Problems#

Solution#

Method 1 – Breadth-First Search (BFS) 1#

Intuition#

Approach#

Code#

Complexity#