You are given an array
colors, in which there are three colors:
You are also given some queries. Each query consists of two integers
c, return the shortest distance between the given index
i and the target color
c. If there is no solution return
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).
Input: colors = [1,2], queries = [[0,3]] Output: [-1] Explanation: There is no 3 in the array.
1 <= colors.length <= 5*10^4
1 <= colors[i] <= 3
1 <= queries.length <= 5*10^4
queries[i].length == 2
0 <= queries[i] < colors.length
1 <= queries[i] <= 3
Build a mapping between color and its indices. Then for each query, do a binary search to find which color index is the nearest one to the query target position.
class Solution: def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]: mapping = defaultdict(list) for i, color in enumerate(colors): mapping[color].append(i) results =  for query in queries: position = query color = query if color not in mapping: results.append(-1) continue index_list = mapping[color] insert = bisect.bisect_left(index_list, position) left_nearest = abs(index_list[max(insert - 1, 0)] - position) right_nearest = abs(index_list[min(insert, len(index_list) - 1)] - position) results.append(min(left_nearest, right_nearest)) return results
- Time Complexity: O(Qlog(N) + N).
- Space Complexity: O(N).
where Q is the length of queries and N is the length of colors.