nikunjsoni

1345

Jun 29th, 2021
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minJumps(vector<int>& arr) {
  4.         int n = arr.size();
  5.         unordered_map<int, vector<int>> indicesOfValue;
  6.         for (int i = 0; i < n; i++)
  7.             indicesOfValue[arr[i]].push_back(i);
  8.         vector<bool> visited(n); visited[0] = true;
  9.         queue<int> q; q.push(0);
  10.         int step = 0;
  11.         while (!q.empty()) {
  12.             int sz = q.size();
  13.             while(sz--) {
  14.                 int i = q.front(); q.pop();
  15.                 if (i == n - 1) return step; // Reached to last index
  16.                 if(i-1 >= 0 && !visited[i-1]){
  17.                     q.push(i-1);
  18.                     visited[i-1] = true;
  19.                 }
  20.                 if(i+1 < n && !visited[i+1]){
  21.                     q.push(i+1);
  22.                     visited[i+1] = true;
  23.                 }
  24.                 for(int j:indicesOfValue[arr[i]]) {
  25.                     if(j >= 0 && j < n && !visited[j]) {
  26.                         visited[j] = true;
  27.                         q.push(j);
  28.                     }
  29.                 }
  30.                 // Very important step to clear the array, else will get TLE.
  31.                 indicesOfValue[arr[i]].clear();
  32.             }
  33.             step++;
  34.         }
  35.         return 0;
  36.     }
  37. };
RAW Paste Data