Jump Game IV - Leetcode 1345 Hard Problem

Problem Statement:

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.

Test Cases:

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

Thought Process:
The first thing came to my mind before looking onto the problem tag is to use a two pointer approach (start, end) and look for the elements that are same. Then move the start pointer to the end pointer and again check for another type elements. Else we need to check the left and right element from the start if possible and again check for the elements if any is present and we can again move the start pointer there.
But this become unclear mainly if we have a duplicate element that appears on the left of the current element and we need the minimum step to reach the last index.
So when I tried to do the code, I couldn't figure out this and got wrong submissions.

Then I decided to look on the hints, problem topic tag and also discuss section and saw that we need to build a graph and also need to do a breadth first search keeping track of the visited node.
Another interesting this is to clear the list in order to prevent stepping back.

Algorithm:

1. base case, if length of array == 1, return 0 as we are already at the end.
2. Build the graph using a map>.
3. Now populate the graph with the array elements and the index.
4. Initialise a queue for the bfs and add index 0.
5. Create a visited array and keep the oth index as true.
6. While queue is not empty: -> Go through the elements of the queue. -> Check whether we are at the last index, if yes return the count of reaching the last index. -> Now lets have a list for storing index of current index value. -> we add both previous and the next values into the list we created. -> Now we go through the elements of this list and check whether its visited or out of bounds or not, if not, then we add them into the queue and mark it as visited. -> Now clear this list. -> Update the count.
7. Finally return the count and it will return 0, if we can't reach the final index in any means.

Code

class Solution {
    public int minJumps(int[] arr) {
        if (arr.length == 1)
            return 0;
        int count = 0;
        int length = arr.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        // populate the graph with index
        for (int i=0; i<length; i++)
            graph.computeIfAbsent(arr[i], x->new LinkedList<>()).add(i);
        // create the boolean array visited
        boolean [] visited = new boolean [length];
        // mark the first element as visited
        visited[0] = true;
        // since we do bfs, we need a queue
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i=size; i>0; i--) {
                int current = queue.poll();
                // if we reach the last index
                if (current == length - 1)
                    return count;
                // get the possible next values
                List<Integer> next = graph.get(arr[current]);
                // now lets add the previous, ie current-1, next ies, current + 1 into the list
                next.add(current-1);
                next.add(current+1);
                for (Integer j:next) {
                    if (j >= 0 && j<length && !visited[j]) {
                        visited[j] = true;
                        queue.offer(j);
                    }
                }
                next.clear(); 
            }
            count += 1;
        }
        return 0;
    }
}

** GitHub Link** : Link