Advertisement
ambition-xx

minJumps

Jan 21st, 2022
755
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>> idx_of_same_val;
  6.         for(int i = 0; i < n; i++){
  7.             idx_of_same_val[arr[i]].push_back(i);
  8.         }
  9.         queue<int> q;
  10.         vector<bool> visited(n, false);
  11.         q.push(0);
  12.         visited[0] = true;
  13.         int steps = 0;
  14.         while(!q.empty()){
  15.             int qsize = q.size();
  16.             for(int i = 0; i < qsize; i++){
  17.                 int t = q.front();
  18.                 q.pop();
  19.                 if(t == n - 1) return steps;
  20.                 if(t + 1 < n && !visited[t + 1]){
  21.                     q.push(t + 1);
  22.                     visited[t + 1] = true;
  23.                 }
  24.                 if(t - 1 >= 0 && !visited[t - 1]){
  25.                     q.push( t - 1 );
  26.                     visited[t - 1] = true;
  27.                 }
  28.                 for(int j = idx_of_same_val[arr[t]].size() - 1; j >= 0 ; j--){
  29.                     if(idx_of_same_val[arr[t]][j] != t && !visited[idx_of_same_val[arr[t]][j]]){
  30.                         q.push(idx_of_same_val[arr[t]][j]);
  31.                         visited[idx_of_same_val[arr[t]][j]] = true;
  32.                     }
  33.                 }
  34.             }
  35.             steps += 1;
  36.         }
  37.         return steps;
  38.     }
  39. };
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement