Closest Equal Element Queries

Intuition

For a query index i, we only care about indices that contain the same value as nums[i].

Among all of those equal elements, the closest one must be either:

• the nearest equal element when moving left
• the nearest equal element when moving right

Because the array is circular, "left" can wrap from index 0 to index n - 1, and "right" can wrap from index n - 1 to index 0.

So the whole problem becomes: for every index, precompute its closest same-value neighbor on the left and on the right.

Approach: Precompute nearest left and right positions

Let:

• left[i] be the nearest index before i with value nums[i]
• right[i] be the nearest index after i with value nums[i]

The annoying part is the circular array. Instead of writing separate wraparound logic, we scan a virtual doubled version of the array.

For left:

1. Traverse from -n to n - 1
2. Store the most recent position of each value in a hash table
3. When i >= 0, the hash table already knows the nearest same value to the left, including wrapped positions

For right:

1. Traverse from 2n - 1 down to 0
2. Store the most recent position of each value in a hash table
3. When i < n, the hash table already knows the nearest same value to the right, including wrapped positions

If a value appears only once, then both searches point exactly one full circle away:

left[i] = i - n
right[i] = i + n

That means the only equal element found is the same index after wrapping around the whole array, so the answer is -1.

Otherwise, the answer is:

min(i - left[i], right[i] - i)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Map<Integer, Integer> lastPosition = new HashMap<>();

        for (int i = -n; i < n; i++) {
            int index = ((i % n) + n) % n;

            if (i >= 0) {
                left[i] = lastPosition.getOrDefault(nums[i], i - n);
            }

            lastPosition.put(nums[index], i);
        }

        lastPosition.clear();

        for (int i = 2 * n - 1; i >= 0; i--) {
            int index = i % n;

            if (i < n) {
                right[i] = lastPosition.getOrDefault(nums[i], i + n);
            }

            lastPosition.put(nums[index], i);
        }

        List<Integer> answer = new ArrayList<>();

        for (int query : queries) {
            if (query - left[query] == n) {
                answer.add(-1);
            } else {
                answer.add(Math.min(query - left[query], right[query] - query));
            }
        }

        return answer;
    }
}

Dry run

Take:

nums = [1, 3, 1, 4, 1, 3, 2]
queries = [0, 3, 5]

Here n = 7.

For value 1, the indices are 0, 2, and 4.

• query 0: nearest equal indices are 2 on the right and 4 through the left wrap
• distances are 2 and 3
• answer is 2

For value 4, the only index is 3.

• query 3: no other index has value 4
• answer is -1

For value 3, the indices are 1 and 5.

• query 5: the nearest equal index is 1 through the wrap
• distance is 3, using path 5 -> 6 -> 0 -> 1
• answer is 3

So the final result is:

[2, -1, 3]

Binary search alternative

Another clean way is to group all indices by value.

For each value, keep a sorted list of its positions. To avoid circular boundary checks, add:

• lastPosition - n at the beginning
• firstPosition + n at the end

Then for each query, binary search the query index inside that value's position list and compare only the immediate previous and next positions.

That approach takes O(n + m log n) time. The preprocessing approach above improves this to O(n + m).

Why this works

For any index i, suppose we want the closest other index with value nums[i].

If we move left from i, the first matching value we encounter is the best possible left-side candidate. Any later match in the same direction is farther away.

The same is true on the right side.

Since every circular path from i starts either by moving left or moving right, the optimal answer must be one of these two nearest neighbors. Precomputing left[i] and right[i] gives us both candidates in constant time for every query.

Complexity Analysis

Let n be the length of nums, and let m be the length of queries.

Time Complexity: O(n + m)

• the left scan visits 2n virtual positions
• the right scan visits 2n virtual positions
• each query is answered in O(1)

Space Complexity: O(n)

• the left and right arrays store one value per index
• the hash table stores the latest position for each distinct number