1182. Shortest Distance to Target Color

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 <= 5*10^4
• 1 <= colors[i] <= 3
• 1 <= queries.length <= 5*10^4
• queries[i].length == 2
• 0 <= queries[i][0] < colors.length
• 1 <= queries[i][1] <= 3

Companies:
Google

Related Topics:
Binary Search

Solution 1. Offline Query

// OJ: https://leetcode.com/problems/shortest-distance-to-target-color/
// Author: github.com/lzl124631x
// Time: O(QlogQ + C + Q)
// Space: O(C)
class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& C, vector<vector<int>>& Q) {
        vector<int> ans(Q.size(), -1);
        for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i);
        sort(begin(Q), end(Q));
        unordered_map<int, int> m;
        for (int i = 0, j = 0; i < C.size() && j < Q.size(); ++i) {
            m[C[i]] = i;
            while (j < Q.size() && Q[j][0] == i) {
                if (m.count(Q[j][1])) ans[Q[j][2]] = i - m[Q[j][1]];
                ++j;
            }
        }
        m.clear();
        for (int i = C.size() - 1, j = Q.size() - 1; i >= 0 && j >= 0; --i) {
            m[C[i]] = i;
            while (j >= 0 && Q[j][0] == i) {
                if (m.count(Q[j][1]) && (ans[Q[j][2]] == -1 || m[Q[j][1]] - i < ans[Q[j][2]])) {
                    ans[Q[j][2]] = m[Q[j][1]] - i;
                }
                --j;
            }
        }
        return ans;
    }
};

TODO

https://leetcode.com/problems/shortest-distance-to-target-color/solution/