Jump Game IV LeetCode solution in Java

1
/*
2
Here we are using map and queue
3
map for storing the array elements and where are the other indices of the same element
4
and queue for BFS
5

6
Initially we start with 0 index
7
So we offer it to the queue
8
Now until the queue is empty we have to do few things for a given position
9
i> check the next index (i+1)
10
ii> check the previous index(i-1)
11
iii> check all the indices of the list whih are present in the map
12
once these three things have been done we will
13
remove the element that is arr[i]
14
because if we did not remove it we are going to do the same repeated task over and over again
15
and this will result in stack overflow
16
so it is important to remove the indices which have been visited once
17
every time we check the queue we incease the answer because viewing a queue means that
18
we are not at the last index
19

20
I hope the idea was clear :) you'll understand better when you see the code
21
*/
22
class Solution {
23
  public int minJumps(int[] arr) {
24
    int n = arr.length;
25

26
    if (n <= 1) return 0;
27
    Map<Integer, List<Integer>> mp = new HashMap<>();
28
    for (int i = 0; i < arr.length; i++) {
29
      if (!mp.containsKey(arr[i])) {
30
        mp.put(arr[i], new ArrayList<>());
31
      }
32
      List<Integer> ls = mp.get(arr[i]);
33
      ls.add(i);
34
    }
35
    // System.out.print(mp);
36
    Queue<Integer> q = new LinkedList<>();
37
    q.offer(0);
38
    int ans = 0;
39
    while (!q.isEmpty()) {
40
      ans++;
41
      int size = q.size();
42
      for (int i = 0; i < size; i++) {
43
        int j = q.poll();
44
        // adding j+1
45
        if (j + 1 < n && mp.containsKey(arr[j + 1])) {
46
          if (j + 1 == n - 1) return ans;
47
          q.offer(j + 1);
48
        }
49
        // adding j-1
50
        if (j - 1 > 0 && mp.containsKey(arr[j - 1])) {
51
          q.offer(j - 1);
52
        }
53

54
        // adding list indices
55
        if (mp.containsKey(arr[j])) {
56
          for (int k : mp.get(arr[j])) {
57
            // if(k == n-1) return ans;
58
            if (k != j) {
59
              if (k == n - 1) return ans;
60
              q.offer(k);
61
            }
62
          }
63
          mp.remove(arr[j]);
64
        }
65
      }
66
    }
67
    return ans;
68
  }
69
}