Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For one value, list all positions where it occurs around the circle. The closest equal element to a queried position must be its previous or next occurrence in that circular order; any farther occurrence requires passing one of those first.

Approach

Scan the array and append each index to its value's position list. The lists are automatically sorted. For each query, return -1 if that value occurs only once. Otherwise binary-search the queried index within its list.

Find the preceding and following entries, wrapping within the position list at either end. For each candidate index, calculate the circular distance as the minimum of its ordinary absolute index difference and n minus that difference. Return the smaller of the two candidate distances. Wrapping the occurrence list is separate from measuring distance around the original array, so gaps of unrelated values are handled correctly.

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        mp = defaultdict(list)
        for i in range(n):
            mp[nums[i]].append(i)

        ans = []
        for q in queries:
            arr = mp[nums[q]]
            if len(arr) == 1:
                ans.append(-1)
            else:
                i = bisect.bisect_left(arr, q)
                prev = arr[(i - 1) % len(arr)]
                next = arr[(i + 1) % len(arr)]
                curr = inf
                d1 = abs(prev - arr[i])
                curr = min(curr, d1, n - d1)
                d2 = abs(next - arr[i])
                curr = min(curr, d2, n - d2)
                ans.append(curr)

        return ans

Complexity analysis

Let n = nums.length, q = queries.length, and f be the maximum frequency of a value. Time: O(n + q log f). Auxiliary space: O(n) excluding the O(q) output.