1134. Shortest Distance to Target Color

• Difficulty: Medium

• Topics: Binary Search

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        unordered_map<int, vector<int>> positions;
        for (int i= 0; i < colors.size(); ++i) {
            positions[colors[i]].push_back(i);
        }

        vector<int> ret;
        for (auto& query : queries) {
            int index = query[0];
            int color = query[1];

            if (positions[color].empty()) {
                ret.push_back(-1);
            } else {
                auto upperBound = upper_bound(positions[color].begin(), positions[color].end(), index);
                auto prevIt = prev(upperBound);
                if (upperBound == positions[color].end()) {
                    ret.push_back(abs(index - *prevIt));
                } else if (upperBound == positions[color].begin()) {
                    ret.push_back(abs(index - *upperBound));
                }
                else {
                     ret.push_back(min(abs(index - *prevIt), abs(index - *upperBound)));
                }
            }
        }

        return ret;
    }
};