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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3

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

Solution

Method 1 – Precompute Nearest Color Indices

Intuition

For each color, precompute the nearest occurrence to the left and right for every index. Then, for each query, the answer is the minimum distance to the nearest occurrence of the target color.

Approach

  1. For each color (1, 2, 3), create two arrays: nearest to the left and nearest to the right.
  2. Fill these arrays by scanning left-to-right and right-to-left.
  3. For each query, compute the minimum distance to the nearest occurrence of the target color.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.*;
class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        int n = colors.length;
        int[][] left = new int[4][n], right = new int[4][n];
        for (int c = 1; c <= 3; ++c) {
            int last = -1;
            for (int i = 0; i < n; ++i) {
                if (colors[i] == c) last = i;
                left[c][i] = last;
            }
            last = -1;
            for (int i = n-1; i >= 0; --i) {
                if (colors[i] == c) last = i;
                right[c][i] = last;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int[] q : queries) {
            int i = q[0], c = q[1];
            int ans = Integer.MAX_VALUE;
            if (left[c][i] != -1) ans = Math.min(ans, Math.abs(i - left[c][i]));
            if (right[c][i] != -1) ans = Math.min(ans, Math.abs(i - right[c][i]));
            res.add(ans == Integer.MAX_VALUE ? -1 : ans);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def shortestDistanceColor(self, colors: list[int], queries: list[list[int]]) -> list[int]:
        n = len(colors)
        left = [[-1]*n for _ in range(4)]
        right = [[-1]*n for _ in range(4)]
        for c in range(1,4):
            last = -1
            for i in range(n):
                if colors[i]==c: last = i
                left[c][i] = last
            last = -1
            for i in range(n-1,-1,-1):
                if colors[i]==c: last = i
                right[c][i] = last
        res = []
        for i,c in queries:
            ans = float('inf')
            if left[c][i]!=-1: ans = min(ans, abs(i-left[c][i]))
            if right[c][i]!=-1: ans = min(ans, abs(i-right[c][i]))
            res.append(-1 if ans==float('inf') else ans)
        return res

Complexity

  • ⏰ Time complexity: O(n + q) — Preprocessing is O(n) per color, each query is O(1).
  • 🧺 Space complexity: O(n) — For the left/right arrays.