1182. Shortest Distance to Target Color.md

1182. Shortest Distance to Target Color, medium

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]] Output: [3,0,3] Explanation: The nearest 3 from index 1 is at index 4 (3 steps away). The nearest 2 from index 2 is at index 2 itself (0 steps away). The nearest 1 from index 6 is at index 3 (3 steps away). Example 2:

Input: colors = [1,2], queries = [[0,3]] Output: [-1] Explanation: There is no 3 in the array.

Constraints:

1 <= colors.length <= 510^4 1 <= colors[i] <= 3 1 <= queries.length <= 510^4 queries[i].length == 2 0 <= queries[i][0] < colors.length 1 <= queries[i][1] <= 3

// 444ms, 93%
class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        const int MAXN = 5*pow(10,4);
        const int N = colors.size();
        int clrs[4] = {0, -1, -1, -1};
        vector<int> neighbors(3*N + 1);
        for (int i = 0; i < colors.size(); i++) {
            int c = colors[i];
            clrs[c] = i;
            for (int j = 0; j < 3; j++) {
                neighbors[3*i + j] = clrs[j+1] >= 0? i - clrs[j+1] : N;
            }
        }
        {
            int clrs[4] = {0, -1, -1, -1};
            for (int i = colors.size()-1; i >= 0; i--) {
                int c = colors[i];
                clrs[c] = i;
                for (int j = 0; j < 3; j++) {
                    neighbors[3*i + j] = min(neighbors[3*i + j], clrs[j+1] >= 0? clrs[j+1] - i : N);
                }
            }
        }
        vector<int> res(queries.size());
        int k = 0;
        for (const auto& q : queries) {
            int i = q[0], c = q[1]-1;
            int r = neighbors[i*3 + c];
            res[k++] = r == N? -1 : r;
        }
        return res;
    }
};