LeetCode 1345. Jump Game IV

, , ,

Question

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

Use BFS. First, we have to record the index of each value and use the queue to BFS and to see which ways we can explore, and also use dp array to store the result. At the end, you can return end.

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
// time:O(n) space:O(n)
    public int minJumps(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int n = arr.length;
        int[] dp = new int[n];// the shortest path to dp[i];
        Arrays.fill(dp, -1);
        HashMap<Integer, List<Integer>> indexOfValue = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexOfValue.computeIfAbsent(arr[i], x -> new LinkedList<>()).add(i);
        }
        Queue<Integer> queue = new LinkedList<>();
        dp[0] = 0;
        queue.offer(0);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            List<Integer> next = indexOfValue.get(arr[curr]);
            // put the curr + 1, curr - 1 and we will validate in the following steps
            next.add(curr - 1);
            next.add(curr + 1);
            for (int index : next) {
                // dp[index] == -1 means we didn't visit yet
                if (index >= 0 && index < n && dp[index] == -1) {
                    dp[index] = dp[curr] + 1;
                    queue.offer(index);
                }
            }
            next.clear();
        }
        return dp[n - 1];
    }

Reference