[LeetCode] 1345. Jump Game IV

 Problem : https://leetcode.com/problems/jump-game-iv/

Covert the array to a graph. Then use BFS find the shortest path.

class Solution {
    public int minJumps(int[] arr) {
        int N = arr.length;
        boolean[] visited = new boolean[N];
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < N; i++) {
            List<Integer> tmp = graph.getOrDefault(arr[i], new ArrayList<Integer>());
            tmp.add(i);
            graph.put(arr[i], tmp);
        }
        
        int step = 0;
        visited[0] = true;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curPos = queue.poll();
                if (curPos == N-1) {
                    return step;
                }
                
                if (curPos - 1 >= 0 && !visited[curPos - 1]) {
                    visited[curPos - 1] = true;
                    queue.offer(curPos - 1);
                }
                
                if (curPos + 1 < N && !visited[curPos + 1]) {
                    visited[curPos + 1] = true;
                    queue.offer(curPos + 1);
                }
                
                for (int nextPos : graph.get(arr[curPos])) {
                    if (nextPos != curPos && !visited[nextPos]) {  
                        visited[nextPos] = true;
                        queue.offer(nextPos);
                    }
                }
                
                // important! 
                // clear the neighbore pos list to avoid redundant visiting.
                graph.get(arr[curPos]).clear(); 
            }
            
            step += 1;
        }
        
        return step;
    }
}