Advertisement
nikunjsoni

1182

May 20th, 2021
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
  4.         int n = colors.size();
  5.         int right[3] = {INT_MIN, INT_MIN, INT_MIN}, left[3] = {INT_MAX, INT_MAX, INT_MAX};
  6.         int dist[n][3];
  7.        
  8.         //  Init distance to -1.
  9.         for(int i=0; i<n; i++)
  10.             for(int j=0; j<3; j++)
  11.                 dist[i][j] = -1;
  12.        
  13.         // Find dist from nearest left color.
  14.         for(int i=0; i<n; i++){
  15.             int color = colors[i]-1;
  16.             left[color] = i;
  17.             for(int j=0; j<3; j++)
  18.                 if(left[j] != INT_MAX)
  19.                     dist[i][j] = i-left[j];
  20.         }
  21.        
  22.         // Find dist from nearest right color.
  23.         for(int i=n-1; i>=0; i--){
  24.             int color = colors[i]-1;
  25.             right[color] = i;
  26.             for(int j=0; j<3; j++){
  27.                 if(right[j] != INT_MIN)
  28.                     if(dist[i][j] == -1 || dist[i][j] > right[j]-i)
  29.                         dist[i][j] = right[j]-i;
  30.             }
  31.         }
  32.        
  33.         // Find ans for each query.
  34.         vector<int> res;
  35.         for(auto q: queries)
  36.             res.push_back(dist[q[0]][q[1]-1]);
  37.         return res;
  38.     }
  39. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement