Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
- int n = colors.size();
- int right[3] = {INT_MIN, INT_MIN, INT_MIN}, left[3] = {INT_MAX, INT_MAX, INT_MAX};
- int dist[n][3];
- // Init distance to -1.
- for(int i=0; i<n; i++)
- for(int j=0; j<3; j++)
- dist[i][j] = -1;
- // Find dist from nearest left color.
- for(int i=0; i<n; i++){
- int color = colors[i]-1;
- left[color] = i;
- for(int j=0; j<3; j++)
- if(left[j] != INT_MAX)
- dist[i][j] = i-left[j];
- }
- // Find dist from nearest right color.
- for(int i=n-1; i>=0; i--){
- int color = colors[i]-1;
- right[color] = i;
- for(int j=0; j<3; j++){
- if(right[j] != INT_MIN)
- if(dist[i][j] == -1 || dist[i][j] > right[j]-i)
- dist[i][j] = right[j]-i;
- }
- }
- // Find ans for each query.
- vector<int> res;
- for(auto q: queries)
- res.push_back(dist[q[0]][q[1]-1]);
- return res;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement