Question

Formatted question description: https://leetcode.ca/all/1345.html

 1345. Jump Game IV

 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.


 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 don't 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.


 Example 4:

 Input: arr = [6,1,9]
 Output: 2


 Example 5:

 Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
 Output: 3


 Constraints:
     1 <= arr.length <= 5 * 104
     -108 <= arr[i] <= 108

Algorithm

Reference: https://leetcode.com/problems/jump-game-iv/solution/

  • store nodes with the same value together in a graph dictionary

First loop over arr to obtain each element and the indices at which the element is in arr. Then loop over arr again to obtain the next indices of each index.

Use dynamic programming. Starting from index 0, each time find the next possible indices that can be jumped to, and update the indices’ minimum jumps. Repeat the process until the last index is reached, and return the number of jumps to reach the last index.

To reduce runtime, consider some special cases first. If arr.length == 1, then the first index is also the last index, so return 0. If the elements at the first index and the last index are the same, then jump once to the last index, so return 1. If the elements at the first index and the second last index are the same, then jump once to the second last index and jump another time to the last index, so return 2.

Code

Java

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return 0;
        }

        // store nodes with the same value together in a graph dictionary
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
        }

        List<Integer> curs = new LinkedList<>(); // store current layer
        curs.add(0);
        Set<Integer> visited = new HashSet<>();
        int step = 0;

        // when current layer exists
        while (!curs.isEmpty()) {
            List<Integer> nex = new LinkedList<>();

            // iterate the layer
            for (int node : curs) {
                // check if index 'node' reached end index
                if (node == n - 1) {
                    return step;
                }

                // 1. check same value
                for (int child : graph.get(arr[node])) {
                    if (!visited.contains(child)) {
                        visited.add(child);
                        nex.add(child);
                    }
                }

                // clear the list to prevent redundant search
                graph.get(arr[node]).clear();

                // 2. check left/right neighbors
                if (node + 1 < n && !visited.contains(node + 1)) {
                    visited.add(node + 1);
                    nex.add(node + 1);
                }
                if (node - 1 >= 0 && !visited.contains(node - 1)) {
                    visited.add(node - 1);
                    nex.add(node - 1);
                }
            }

            curs = nex;
            step++;
        }

        return -1;
    }
}

Java

class Solution {
    public int minJumps(int[] arr) {
        if (arr.length == 1)
            return 0;
        int length = arr.length;
        if (arr[0] == arr[length - 1])
            return 1;
        else if (arr[0] == arr[length - 2])
            return 2;
        Map<Integer, List<Integer>> valueIndicesMap = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < length; i++) {
            int num = arr[i];
            List<Integer> indices = valueIndicesMap.getOrDefault(num, new ArrayList<Integer>());
            indices.add(i);
            valueIndicesMap.put(num, indices);
        }
        Map<Integer, Set<Integer>> nextJumpMap = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < length; i++) {
            Set<Integer> nextJump = new HashSet<Integer>();
            if (i > 0)
                nextJump.add(i - 1);
            if (i < length - 1)
                nextJump.add(i + 1);
            int num = arr[i];
            List<Integer> indices = valueIndicesMap.getOrDefault(num, new ArrayList<Integer>());
            for (int index : indices) {
                if (index != i)
                    nextJump.add(index);
            }
            nextJumpMap.put(i, nextJump);
        }
        int[] dp = new int[length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int index = queue.poll();
                int curSteps = dp[index] + 1;
                Set<Integer> nextJump = nextJumpMap.getOrDefault(index, new HashSet<Integer>());
                for (int nextIndex : nextJump) {
                    int prevSteps = dp[nextIndex];
                    if (curSteps < prevSteps) {
                        dp[nextIndex] = curSteps;
                        queue.offer(nextIndex);
                    }
                }
            }
        }
        return dp[length - 1];
    }
}

All Problems

All Solutions