3488. Closest Equal Element Queries

Array
Hash Table

TIME

O(n + q)

SPACE

O(n)

Intuition

Precompute the minimum distance to a same-value element for every index. Then queries are O(1) lookups.

Solution

Step 1: Group Indices by Value

indices = defaultdict(list)
for i, num in enumerate(nums):
    indices[num].append(i)

Step 2: Precompute Minimum Distances

For each value with 2+ occurrences:

Indices are sorted (we add them in order)
For each index, check distance to previous and next (circular)
Store minimum in min_dist[i]

for idx_list in indices.values():
    if len(idx_list) < 2:
        continue  # no same-value neighbor
    
    for k, i in enumerate(idx_list):
        prev = idx_list[k - 1]  # wraps around in Python
        nxt = idx_list[(k + 1) % len(idx_list)]
        
        dist_prev = min((i - prev) % n, (prev - i) % n)
        dist_next = min((nxt - i) % n, (i - nxt) % n)
        min_dist[i] = min(dist_prev, dist_next)

Step 3: Answer Queries

return [min_dist[q] for q in queries]

Complexity

Time: O(n + q), precompute O(n), queries O(q)
Space: O(n)

Edge Cases

Unique values → all -1
All same value → check prev and next neighbors
Two occurrences of a value → both point to each other

Code

from typing import List
from collections import defaultdict


class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        """
        3488. Closest Equal Element Queries
        Time: O(n + q)
        Space: O(n)
        """
        n = len(nums)

        # Group indices by value
        indices = defaultdict(list)
        for i, num in enumerate(nums):
            indices[num].append(i)

        # Precompute minimum distance for each index
        min_dist = [-1] * n

        for idx_list in indices.values():
            if len(idx_list) < 2:
                continue

            m = len(idx_list)
            for k, i in enumerate(idx_list):
                prev_idx = idx_list[k - 1]
                next_idx = idx_list[(k + 1) % m]

                # Circular distance to previous
                dist_prev = (i - prev_idx) % n
                dist_prev = min(dist_prev, n - dist_prev)

                # Circular distance to next
                dist_next = (next_idx - i) % n
                dist_next = min(dist_next, n - dist_next)

                min_dist[i] = min(dist_prev, dist_next)

        return [min_dist[q] for q in queries]

import java.util.*;

/**
 * 3488. Closest Equal Element Queries
 * Time: O(n + q)
 * Space: O(n)
 */
class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;

        // Group indices by value
        Map<Integer, List<Integer>> indices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        // Precompute minimum distance for each index
        int[] minDist = new int[n];
        Arrays.fill(minDist, -1);

        for (List<Integer> idxList : indices.values()) {
            if (idxList.size() < 2) continue;

            int m = idxList.size();
            for (int k = 0; k < m; k++) {
                int i = idxList.get(k);
                int prevIdx = idxList.get((k - 1 + m) % m);
                int nextIdx = idxList.get((k + 1) % m);

                // Circular distance to previous
                int distPrev = (i - prevIdx + n) % n;
                distPrev = Math.min(distPrev, n - distPrev);

                // Circular distance to next
                int distNext = (nextIdx - i + n) % n;
                distNext = Math.min(distNext, n - distNext);

                minDist[i] = Math.min(distPrev, distNext);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int q : queries) {
            result.add(minDist[q]);
        }
        return result;
    }
}