Algorithm
Closest Equal Element Queries
Solution
class Solution:
def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
nums_pos = defaultdict(list)
for i in range(n):
nums_pos[nums[i]].append(i)
for pos in nums_pos.values():
x = pos[0]
pos.insert(0, pos[-1] - n)
pos.append(x + n)
for i in range(len(queries)):
x = nums[queries[i]]
pos_list = nums_pos[x]
if len(pos_list) == 3:
queries[i] = -1
continue
pos = bisect.bisect_left(pos_list, queries[i])
queries[i] = min(
pos_list[pos + 1] - pos_list[pos],
pos_list[pos] - pos_list[pos - 1],
)
return queriesVideo GuideLeetcode Daily
Time Complexity
O(N + M log N (Approach 1)
Space Complexity
O(N)
