Jump Game IV LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minJumps(vector<int> &arr) {
4
    int n = arr.size();
5
    unordered_map<int, vector<int>> mp;
6
    for (int i = 0; i < n; i++) mp[arr[i]].push_back(i);
7

8
    queue<int> q;
9
    vector<bool> visited(n, false);
10
    q.push(0);
11
    int steps = 0;
12
    while (!q.empty()) {
13
      int size = q.size();
14
      while (size--) {
15
        int currIdx = q.front();
16
        q.pop();
17
        if (currIdx == n - 1) return steps;
18
        //================================================================
19
        // EXPLORE ALL POSSIBLE OPTIONS
20
        if (currIdx + 1 < n && !visited[currIdx + 1]) // OPTION-1 (Move Forward)
21
        {
22
          visited[currIdx + 1] = true;
23
          q.push(currIdx + 1);
24
        }
25
        if (currIdx - 1 >= 0 && !visited[currIdx - 1]) // OPTION-2 (Move Backward)
26
        {
27
          visited[currIdx - 1] = true;
28
          q.push(currIdx - 1);
29
        }
30
        for (int newIdx : mp[arr[currIdx]]) // OPTION-3 (Move to same valued idx)
31
        {                                   // newIdx coud be before currIdx or after currIdx
32
          if (!visited[newIdx]) {
33
            visited[newIdx] = true;
34
            q.push(newIdx);
35
          }
36
        }
37
        //===================================================================
38
        mp[arr[currIdx]].clear(); // EXPLAINED BELOW :)
39
      }
40
      steps++;
41
    }
42
    return -1;
43
  }
44
};