Problem

You are given a circular array nums and an array queries.

For each query i, you have to find the following:

  • The minimum distance between the element at index queries[i] and any other index j in the circular array, where nums[j] == nums[queries[i]]. If no such index exists, the answer for that query should be -1.

Return an array answer of the same size as queries, where answer[i] represents the result for query i.

Example 1

1
2
3
4
5
6

Input: nums = [1,3,1,4,1,3,2], queries = [0,3,5]
Output: [2,-1,3]
Explanation:
* Query 0: The element at `queries[0] = 0` is `nums[0] = 1`. The nearest index with the same value is 2, and the distance between them is 2.
* Query 1: The element at `queries[1] = 3` is `nums[3] = 4`. No other index contains 4, so the result is -1.
* Query 2: The element at `queries[2] = 5` is `nums[5] = 3`. The nearest index with the same value is 1, and the distance between them is 3 (following the circular path: `5 -> 6 -> 0 -> 1`).

Example 2

1
2
3
4
5

Input: nums = [1,2,3,4], queries = [0,1,2,3]
Output: [-1,-1,-1,-1]
Explanation:
Each value in `nums` is unique, so no index shares the same value as the
queried element. This results in -1 for all queries.

Constraints

  • 1 <= queries.length <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 0 <= queries[i] < nums.length

Examples

Solution

Method 1 – Hash Map + Binary Search

Intuition

For each value in nums, store all its indices. For each query, use binary search to find the closest index (other than itself) with the same value, considering the circular nature of the array.

Approach

  1. Build a hash map from value to a sorted list of indices where it appears.
  2. For each query index q, get the list of indices for nums[q].
  3. If the list has only one index, answer is -1.
  4. Use binary search to find the closest index to q in the list (excluding itself).
  5. Compute the circular distance for both the next and previous indices in the list.
  6. Return the minimum such distance for each query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> closestEqualElementQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; ++i) pos[nums[i]].push_back(i);
        vector<int> ans;
        for (int q : queries) {
            auto& v = pos[nums[q]];
            if (v.size() == 1) { ans.push_back(-1); continue; }
            auto it = lower_bound(v.begin(), v.end(), q);
            int d1 = INT_MAX, d2 = INT_MAX;
            if (it != v.end() && *it != q) d1 = min(abs(*it - q), n - abs(*it - q));
            if (it != v.begin()) {
                int prev = *(--it);
                if (prev != q) d2 = min(abs(prev - q), n - abs(prev - q));
            }
            ans.push_back(min(d1, d2));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public List<Integer> closestEqualElementQueries(int[] nums, int[] queries) {
        int n = nums.length;
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        List<Integer> ans = new ArrayList<>();
        for (int q : queries) {
            List<Integer> v = pos.get(nums[q]);
            if (v.size() == 1) { ans.add(-1); continue; }
            int idx = Collections.binarySearch(v, q);
            int d1 = Integer.MAX_VALUE, d2 = Integer.MAX_VALUE;
            if (idx + 1 < v.size()) d1 = Math.min(Math.abs(v.get(idx + 1) - q), n - Math.abs(v.get(idx + 1) - q));
            if (idx - 1 >= 0) d2 = Math.min(Math.abs(v.get(idx - 1) - q), n - Math.abs(v.get(idx - 1) - q));
            ans.add(Math.min(d1, d2));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def closestEqualElementQueries(self, nums: list[int], queries: list[int]) -> list[int]:
        from bisect import bisect_left
        n = len(nums)
        pos = {}
        for i, v in enumerate(nums):
            pos.setdefault(v, []).append(i)
        ans = []
        for q in queries:
            v = pos[nums[q]]
            if len(v) == 1:
                ans.append(-1)
                continue
            idx = bisect_left(v, q)
            d1 = d2 = float('inf')
            if idx < len(v) - 1:
                d1 = min(abs(v[idx + 1] - q), n - abs(v[idx + 1] - q))
            if idx > 0:
                d2 = min(abs(v[idx - 1] - q), n - abs(v[idx - 1] - q))
            ans.append(min(d1, d2))
        return ans

Complexity

  • ⏰ Time complexity: O(n + q log k), where n = len(nums), q = len(queries), k = max frequency of any value.
  • 🧺 Space complexity: O(n), for the hash map.