package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 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 * 10^4
 * -10^8 <= arr[i] <= 10^8
 * */
public class _1345 {
    public static class Solution1 {
        /**credit: https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC%2B%2B-BFS-Solution-Clean-code-O(N)*/
        public int minJumps(int[] arr) {
            Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                valueToIndices.computeIfAbsent(arr[i], k -> new LinkedList<>()).add(i);
            }
            boolean[] visited = new boolean[arr.length];
            Queue<Integer> indexQueue = new LinkedList<>();
            indexQueue.offer(0);
            int steps = 0;
            while (!indexQueue.isEmpty()) {
                int size = indexQueue.size();
                for (int i = 0; i < size; i++) {
                    int index = indexQueue.poll();
                    if (index == arr.length - 1) {
                        return steps;
                    }
                    List<Integer> nextPossibleIndices = valueToIndices.get(arr[index]);
                    nextPossibleIndices.add(index - 1);
                    nextPossibleIndices.add(index + 1);
                    for (int next : nextPossibleIndices) {
                        if (next >= 0 && next < arr.length && !visited[next]) {
                            visited[next] = true;
                            indexQueue.offer(next);
                        }
                    }
                    nextPossibleIndices.clear();//this line is the key to this entire algorithm to avoid TLE, explanation: https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC++-BFS-Solution-Clean-code-O(N)/445620
                }
                steps++;
            }
            return 0;
        }
    }
}

@@ -158,1126 +158,8 @@
 e;%0A%0A
-/**%0A * 1345. Jump Game IV%0A *%0A * Given an array of integers arr, you are initially positioned at the first index of the array.%0A * In one step you can jump from index i to index:%0A * i + 1 where: i + 1 %3C arr.length.%0A * i - 1 where: i - 1 %3E= 0.%0A * j where: arr%5Bi%5D == arr%5Bj%5D and i != j.%0A * Return the minimum number of steps to reach the last index of the array.%0A * Notice that you can not jump outside of the array at any time.%0A *%0A * Example 1:%0A * Input: arr = %5B100,-23,-23,404,100,23,23,23,3,404%5D%0A * Output: 3%0A * Explanation: You need three jumps from index 0 --%3E 4 --%3E 3 --%3E 9. Note that index 9 is the last index of the array.%0A *%0A * Example 2:%0A * Input: arr = %5B7%5D%0A * Output: 0%0A * Explanation: Start index is the last index. You don't need to jump.%0A *%0A * Example 3:%0A * Input: arr = %5B7,6,9,6,9,6,9,7%5D%0A * Output: 1%0A * Explanation: You can jump directly from index 0 to index 7 which is last index of the array.%0A *%0A * Example 4:%0A * Input: arr = %5B6,1,9%5D%0A * Output: 2%0A *%0A * Example 5:%0A * Input: arr = %5B11,22,7,7,7,7,7,7,7,22,13%5D%0A * Output: 3%0A *%0A * Constraints:%0A * 1 %3C= arr.length %3C= 5 * 10%5E4%0A * -10%5E8 %3C= arr%5Bi%5D %3C= 10%5E8%0A * */%0A
 publ
@@ -222,16 +222,28 @@
      /**
+%0A         * 
 credit: 
@@ -340,16 +340,26 @@
 ode-O(N)
+%0A         
 */%0A     

refactor 1345