Problem Statement in English

You’re given a 0-indexed integer array nums and a 0-indexed integer array queries. The i-th query is represented as a single integer queries[i]. For each query, you need to find the closest index j such that j != i and nums[j] == nums[i]. The distance between two indices i and j is defined as abs(i - j), where abs(x) is the absolute value of x. If there are multiple answers, return the minimum distance. If there is no answer, return -1.

Perform this for all queries and return an array of answers.

Approach

We can first create a hashmap where the key is the value of the element and the value is a list of indices where that element occurs.

Then, for each query, we can use binary search on the list of indices for that value to find the closest index of the same value and calculate the distance.

We can employ a simple formula to calculate the circular distance which is the number of elements in the array minus the linear distance.

And we’re done!

Solution in Python


class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        hm = defaultdict(list)
        N = len(nums)

        for i, v in enumerate(nums):
            hm[v].append(i)

        res = []

        for q in queries:
            v = nums[q]
            arr = hm[v]

            L = len(arr)

            pos = bisect_left(arr, q)
            
            prev = arr[(pos - 1 + L) % L]
            next = arr[(pos + 1) % L]

            ldp = abs(q - prev)
            cdp = N - ldp

            ldn = abs(q - next)
            cdn = N - ldn

            answer = min(ldp, cdp, ldn, cdn)

            res.append(answer if answer != 0 else -1)

        return res

Complexity

  • Time: $O(N \log N)$
    Since we sort the indices for each value and perform binary search for each query.

  • Space: $O(N)$
    Since we store the indices for each value in a hashmap.

Mistakes I Made

I used L instead of N in the formula for circular distance, which was incorrect. The circular distance should be calculated based on the total number of elements in the original array, not the number of occurrences in the list of all occurrences of that value.

And we are done.