Given a list of colors represented as an integer array colors, where each color is either 1, 2, or 3, and a list of queries queries where each query is a pair [index, targetColor], you are to return an array of answers. For each query, find the shortest distance from colors[index] to any occurrence of targetColor in colors. The distance between two indices i and j is |i - j|. If the target color does not exist in colors, return -1 for that query.
colors can be large, and there can be many queries.
The problem asks for the shortest distance from a given index to a target color for multiple queries. A brute-force approach would be, for each query, to scan the entire colors array and find the closest occurrence of targetColor. However, this is inefficient if there are many queries or the array is large.
To optimize, we can preprocess the colors array to quickly answer each query. The key insight is that the set of possible colors is small (1, 2, 3), so we can, for each color, precompute the closest occurrence to the left and right of every position. This will let us answer each query in constant time.
left and right.left[i][c] stores the closest occurrence (index) of color c to the left of or at position i.right[i][c] stores the closest occurrence (index) of color c to the right of or at position i.left with -1 for all positions and colors, and similarly for right.left by scanning colors from left to right, updating the last seen position for each color.right by scanning from right to left.[index, targetColor]:
targetColor to the left (or at) index using left[index][targetColor].index using right[index][targetColor].-1, return -1.O(1) time after O(N) preprocessing, where N is the length of colors.
Input: colors = [1, 1, 2, 1, 3, 2, 2, 3, 3], queries = [[1, 3], [2, 2], [6, 1]]
[1, 3]
-1), to the right: index 4.|1 - 4| = 3.[2, 2]
[6, 1]
|6 - 3| = 3.[3, 0, 3]colors array: O(QN) where Q is the number of queries, N is the length of colors.O(N) for each color (constant number), so overall O(N).O(1) lookup and computation.O(N + Q).O(N) for the left/right arrays.By recognizing the small, fixed set of colors and leveraging preprocessing, we can efficiently answer each query in constant time. The key insight is to precompute, for every position, the closest occurrence of each color to the left and right. This approach avoids repeated scans and reduces the overall complexity from quadratic to linear, making it highly efficient for large datasets and many queries.
class Solution:
def shortestDistanceColor(self, colors, queries):
n = len(colors)
max_color = 3 # colors are 1,2,3
# Precompute left and right nearest indices for each color
left = [[-1]*(max_color+1) for _ in range(n)]
right = [[-1]*(max_color+1) for _ in range(n)]
last_seen = [-1]*(max_color+1)
for i in range(n):
last_seen[colors[i]] = i
for c in range(1, max_color+1):
left[i][c] = last_seen[c]
last_seen = [-1]*(max_color+1)
for i in range(n-1, -1, -1):
last_seen[colors[i]] = i
for c in range(1, max_color+1):
right[i][c] = last_seen[c]
res = []
for idx, target in queries:
l = left[idx][target]
r = right[idx][target]
ans = float('inf')
if l != -1:
ans = min(ans, abs(idx - l))
if r != -1:
ans = min(ans, abs(idx - r))
res.append(ans if ans != float('inf') else -1)
return res
class Solution {
public:
vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
int n = colors.size();
int max_color = 3;
vector<vector<int>> left(n, vector<int>(max_color+1, -1));
vector<vector<int>> right(n, vector<int>(max_color+1, -1));
vector<int> last_seen(max_color+1, -1);
for (int i = 0; i < n; ++i) {
last_seen[colors[i]] = i;
for (int c = 1; c <= max_color; ++c)
left[i][c] = last_seen[c];
}
fill(last_seen.begin(), last_seen.end(), -1);
for (int i = n-1; i >= 0; --i) {
last_seen[colors[i]] = i;
for (int c = 1; c <= max_color; ++c)
right[i][c] = last_seen[c];
}
vector<int> res;
for (auto& q : queries) {
int idx = q[0], target = q[1];
int l = left[idx][target];
int r = right[idx][target];
int ans = INT_MAX;
if (l != -1) ans = min(ans, abs(idx - l));
if (r != -1) ans = min(ans, abs(idx - r));
res.push_back(ans == INT_MAX ? -1 : ans);
}
return res;
}
};
class Solution {
public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
int n = colors.length;
int maxColor = 3;
int[][] left = new int[n][maxColor+1];
int[][] right = new int[n][maxColor+1];
int[] lastSeen = new int[maxColor+1];
Arrays.fill(lastSeen, -1);
for (int i = 0; i < n; i++) {
lastSeen[colors[i]] = i;
for (int c = 1; c <= maxColor; c++)
left[i][c] = lastSeen[c];
}
Arrays.fill(lastSeen, -1);
for (int i = n-1; i >= 0; i--) {
lastSeen[colors[i]] = i;
for (int c = 1; c <= maxColor; c++)
right[i][c] = lastSeen[c];
}
List<Integer> res = new ArrayList<>();
for (int[] q : queries) {
int idx = q[0], target = q[1];
int l = left[idx][target];
int r = right[idx][target];
int ans = Integer.MAX_VALUE;
if (l != -1) ans = Math.min(ans, Math.abs(idx - l));
if (r != -1) ans = Math.min(ans, Math.abs(idx - r));
res.add(ans == Integer.MAX_VALUE ? -1 : ans);
}
return res;
}
}
var shortestDistanceColor = function(colors, queries) {
const n = colors.length, maxColor = 3;
const left = Array.from({length: n}, () => Array(maxColor+1).fill(-1));
const right = Array.from({length: n}, () => Array(maxColor+1).fill(-1));
let lastSeen = Array(maxColor+1).fill(-1);
for (let i = 0; i < n; i++) {
lastSeen[colors[i]] = i;
for (let c = 1; c <= maxColor; c++)
left[i][c] = lastSeen[c];
}
lastSeen = Array(maxColor+1).fill(-1);
for (let i = n-1; i >= 0; i--) {
lastSeen[colors[i]] = i;
for (let c = 1; c <= maxColor; c++)
right[i][c] = lastSeen[c];
}
const res = [];
for (const [idx, target] of queries) {
const l = left[idx][target], r = right[idx][target];
let ans = Number.POSITIVE_INFINITY;
if (l !== -1) ans = Math.min(ans, Math.abs(idx - l));
if (r !== -1) ans = Math.min(ans, Math.abs(idx - r));
res.push(ans === Number.POSITIVE_INFINITY ? -1 : ans);
}
return res;
};