# Closest Equal Element Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/closest-equal-element-queries)
Canonical: https://scaleengineer.com/dsa/problems/closest-equal-element-queries
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## 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:**

**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:**

**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 <= 105`
* `1 <= nums[i] <= 106`
* `0 <= queries[i] < nums.length`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. For each query, it iterates through the entire `nums` array to find all other elements equal to the one at the queried index. It calculates the circular distance to each of these matching elements and keeps track of the minimum distance found.
**Time:** O(Q * N), where `Q` is the number of queries and `N` is the length of `nums`. For each of the `Q` queries, we perform a linear scan of the `N` elements. · **Space:** O(Q) for the answer array. If we exclude the output array, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Very inefficient due to nested loops.; Will result in a 'Time Limit Exceeded' error for large inputs as per the problem constraints.
### Explanation
The algorithm processes one query at a time. For a given `queryIndex`, it first identifies the target value `val = nums[queryIndex]`. It then loops through every other index `j` in the `nums` array. If `nums[j]` is equal to `val`, it calculates the distance between `queryIndex` and `j`. Since the array is circular, the distance between two indices `i` and `j` in an array of length `n` is `min(|i - j|, n - |i - j|)`. A variable `minDist` is maintained to store the minimum distance found so far for the current query. It's initialized to a very large value. After checking all indices, if `minDist` remains at its initial large value, it means no other equal element was found, and the result is -1. Otherwise, the result is `minDist`. This process is repeated for all queries.

```java
class Solution {
    public int[] closestEqualElements(int[] nums, int[] queries) {
        int n = nums.length;
        int q = queries.length;
        int[] answer = new int[q];

        for (int i = 0; i < q; i++) {
            int queryIndex = queries[i];
            int targetVal = nums[queryIndex];
            int minDistance = Integer.MAX_VALUE;

            for (int j = 0; j < n; j++) {
                if (j == queryIndex) {
                    continue;
                }
                if (nums[j] == targetVal) {
                    int dist = Math.abs(queryIndex - j);
                    int circularDist = Math.min(dist, n - dist);
                    minDistance = Math.min(minDistance, circularDist);
                }
            }

            if (minDistance == Integer.MAX_VALUE) {
                answer[i] = -1;
            } else {
                answer[i] = minDistance;
            }
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an `answer` array of the same size as `queries`.
- Let `n` be the length of `nums`.
- For each `i` from `0` to `queries.length - 1`:
  - Let `queryIndex = queries[i]`.
  - Let `targetVal = nums[queryIndex]`.
  - Initialize `minDist = Integer.MAX_VALUE`.
  - For each `j` from `0` to `n - 1`:
    - If `j == queryIndex`, continue.
    - If `nums[j] == targetVal`:
      - `dist = Math.abs(queryIndex - j)`.
      - `circularDist = Math.min(dist, n - dist)`.
      - `minDist = Math.min(minDist, circularDist)`.
  - Set `answer[i]` to `minDist` if it was updated, otherwise set it to `-1`.
- Return `answer`.

## Pre-computation with Hash Map and Binary Search
This approach improves upon the brute-force method by avoiding the repeated scanning of the `nums` array. It first preprocesses the `nums` array to store the indices of each unique value in a hash map. The lists of indices are inherently sorted. For each query, it uses binary search on the corresponding list of indices to efficiently find the nearest neighbors.
**Time:** O(N + Q * log N). `O(N)` for preprocessing the `nums` array into the hash map. For each of the `Q` queries, we perform a binary search on a list of indices, which takes `O(log k)` time, where `k` is the number of occurrences of the value. In the worst case, `k` can be up to `N`. · **Space:** O(N) to store the hash map. In the worst case, every element is distinct, and the map stores `N` keys, each with a list of one index.
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass the given constraints.
**Cons:** Requires extra space for the hash map.
### Explanation
### Preprocessing:
1.  Create a hash map, `valToIndices`, where keys are the integer values from `nums` and values are lists of indices where those values appear.
2.  Iterate through `nums`. For each element `nums[i]`, add the index `i` to the list associated with `nums[i]` in the map. Since we iterate from `i=0` to `n-1`, the lists of indices will be sorted.

### Query Processing:
1.  For each `queryIndex` in `queries`, get the value `val = nums[queryIndex]`.
2.  Retrieve the list of indices, `indicesList`, for `val` from the hash map.
3.  If `indicesList` contains one or zero elements, no other equal element exists, so the answer is -1.
4.  Otherwise, the closest indices to `queryIndex` must be its immediate predecessor and successor in the sorted `indicesList`. The circular nature of the array means the predecessor of the first element is the last, and the successor of the last is the first.
5.  Use binary search (`Collections.binarySearch`) to find the position of `queryIndex` within `indicesList`. Let this position be `listIdx`.
6.  Identify the predecessor index in `nums` (`prevNumIndex`) and the successor index (`nextNumIndex`) using `listIdx` and handling wrap-around.
7.  The distance to the left neighbor is `(queryIndex - prevNumIndex + n) % n`.
8.  The distance to the right neighbor is `(nextNumIndex - queryIndex + n) % n`.
9.  The minimum of these two distances is the answer for the query.

```java
import java.util.*;

class Solution {
    public int[] closestEqualElements(int[] nums, int[] queries) {
        int n = nums.length;
        int q = queries.length;
        Map<Integer, List<Integer>> valToIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int[] answer = new int[q];
        for (int i = 0; i < q; i++) {
            int queryIndex = queries[i];
            int val = nums[queryIndex];
            List<Integer> indices = valToIndices.get(val);

            if (indices.size() <= 1) {
                answer[i] = -1;
                continue;
            }

            int listIdx = Collections.binarySearch(indices, queryIndex);
            
            int listSize = indices.size();
            int prevNumIndex = indices.get((listIdx - 1 + listSize) % listSize);
            int nextNumIndex = indices.get((listIdx + 1) % listSize);

            int distLeft = (queryIndex - prevNumIndex + n) % n;
            int distRight = (nextNumIndex - queryIndex + n) % n;
            
            answer[i] = Math.min(distLeft, distRight);
        }
        return answer;
    }
}
```
### Algorithm
- Create a `Map<Integer, List<Integer>> valToIndices`.
- Iterate `i` from `0` to `nums.length - 1` and populate the map: `valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i)`.
- Initialize an `answer` array.
- For each `queryIndex` in `queries`:
  - Get `val = nums[queryIndex]` and `indices = valToIndices.get(val)`.
  - If `indices.size() <= 1`, the answer is -1.
  - Otherwise, find the position of `queryIndex` in `indices` using binary search, let it be `listIdx`.
  - Get the predecessor index in `nums`: `prevNumIndex = indices.get((listIdx - 1 + indices.size()) % indices.size())`.
  - Get the successor index in `nums`: `nextNumIndex = indices.get((listIdx + 1) % indices.size())`.
  - Calculate left distance: `distLeft = (queryIndex - prevNumIndex + n) % n`.
  - Calculate right distance: `distRight = (nextNumIndex - queryIndex + n) % n`.
  - The answer is `Math.min(distLeft, distRight)`.
- Return `answer`.

## Full Pre-computation of All Answers
This is the most optimal approach. Instead of calculating the answer for each query as it comes, we can pre-calculate the answer for every possible index in the `nums` array. This way, answering the queries becomes a simple lookup in the pre-calculated results array.
**Time:** O(N + Q). `O(N)` to build the map. `O(N)` to iterate through all the indices in the map's values to compute `allAnswers` (since the total number of indices is `N`). `O(Q)` to build the final result from `allAnswers`. · **Space:** O(N + Q). `O(N)` for the hash map, `O(N)` for the `allAnswers` array, and `O(Q)` for the result array. If we exclude the output array, it's `O(N)`.
**Pros:** Most efficient time complexity, as it's linear with respect to the input sizes.; Queries are answered in O(1) time after pre-computation.
**Cons:** Uses more space than the binary search approach due to the `allAnswers` array.
### Explanation
The core idea is to compute the closest distance for every index `i` from `0` to `n-1` and store it in an `allAnswers` array.

### Preprocessing:
1.  First, just like the previous approach, we create a hash map `valToIndices` to group indices by their values. This takes `O(N)` time.

### Answer Calculation:
1.  Initialize an `allAnswers` array of size `n` with a default value of -1.
2.  Iterate through each list of indices in the `valToIndices` map.
3.  For each `indicesList` that has more than one element:
    - Iterate through the `indicesList`. For each `currentIndex` at position `j` in the list:
    - Find its predecessor `prevIndex` and successor `nextIndex` in the list, handling wrap-around for the first and last elements.
    - The predecessor is at `indicesList.get((j - 1 + size) % size)`.
    - The successor is at `indicesList.get((j + 1) % size)`.
    - Calculate the distance to the left neighbor: `distLeft = (currentIndex - prevIndex + n) % n`.
    - Calculate the distance to the right neighbor: `distRight = (nextIndex - currentIndex + n) % n`.
    - The minimum distance for `currentIndex` is `min(distLeft, distRight)`. Store this value in `allAnswers[currentIndex]`.

### Query Resolution:
1.  After the `allAnswers` array is fully computed, iterate through the `queries` array.
2.  For each `queryIndex`, the result is simply `allAnswers[queryIndex]`.

```java
import java.util.*;

class Solution {
    public int[] closestEqualElements(int[] nums, int[] queries) {
        int n = nums.length;
        Map<Integer, List<Integer>> valToIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int[] allAnswers = new int[n];
        Arrays.fill(allAnswers, -1);

        for (List<Integer> indices : valToIndices.values()) {
            int listSize = indices.size();
            if (listSize <= 1) {
                continue;
            }
            for (int i = 0; i < listSize; i++) {
                int currentIndex = indices.get(i);
                int prevIndex = indices.get((i - 1 + listSize) % listSize);
                int nextIndex = indices.get((i + 1) % listSize);

                int distLeft = (currentIndex - prevIndex + n) % n;
                int distRight = (nextIndex - currentIndex + n) % n;
                
                allAnswers[currentIndex] = Math.min(distLeft, distRight);
            }
        }

        int q = queries.length;
        int[] result = new int[q];
        for (int i = 0; i < q; i++) {
            result[i] = allAnswers[queries[i]];
        }
        return result;
    }
}
```
### Algorithm
- Create a `Map<Integer, List<Integer>> valToIndices` and populate it by iterating through `nums`.
- Initialize an `allAnswers` array of size `n` with `-1`.
- Let `n = nums.length`.
- For each `List<Integer> indices` in `valToIndices.values()`:
  - If `indices.size() <= 1`, continue.
  - Let `listSize = indices.size()`.
  - For `j` from `0` to `listSize - 1`:
    - `currentIndex = indices.get(j)`.
    - `prevIndex = indices.get((j - 1 + listSize) % listSize)`.
    - `nextIndex = indices.get((j + 1) % listSize)`.
    - `distLeft = (currentIndex - prevIndex + n) % n`.
    - `distRight = (nextIndex - currentIndex + n) % n`.
    - `allAnswers[currentIndex] = Math.min(distLeft, distRight)`.
- Create a `result` array of size `queries.length`.
- For `i` from `0` to `queries.length - 1`:
  - `result[i] = allAnswers[queries[i]]`.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> solveQueries(int[] nums, int[] queries) {
    int n = nums.length;
    int m = n * 2;
    int[] d = new int[m];
    Arrays.fill(d, m);
    Map<Integer, Integer> left = new HashMap<>();
    for (int i = 0; i < m; i++) {
      int x = nums[i % n];
      if (left.containsKey(x)) {
        d[i] = Math.min(d[i], i - left.get(x));
      }
      left.put(x, i);
    }
    Map<Integer, Integer> right = new HashMap<>();
    for (int i = m - 1; i >= 0; i--) {
      int x = nums[i % n];
      if (right.containsKey(x)) {
        d[i] = Math.min(d[i], right.get(x) - i);
      }
      right.put(x, i);
    }
    for (int i = 0; i < n; i++) {
      d[i] = Math.min(d[i], d[i + n]);
    }
    List<Integer> ans = new ArrayList<>();
    for (int query : queries) {
      ans.add(d[query] >= n ? -1 : d[query]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> solveQueries(vector<int> &nums, vector<int> &queries) {
    int n = nums.size();
    int m = n * 2;
    vector<int> d(m, m);
    unordered_map<int, int> left;
    for (int i = 0; i < m; i++) {
      int x = nums[i % n];
      if (left.count(x)) {
        d[i] = min(d[i], i - left[x]);
      }
      left[x] = i;
    }
    unordered_map<int, int> right;
    for (int i = m - 1; i >= 0; i--) {
      int x = nums[i % n];
      if (right.count(x)) {
        d[i] = min(d[i], right[x] - i);
      }
      right[x] = i;
    }
    for (int i = 0; i < n; i++) {
      d[i] = min(d[i], d[i + n]);
    }
    vector<int> ans;
    for (int query : queries) {
      ans.push_back(d[query] >= n ? -1 : d[query]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]: n = len(nums) m = n << 1 d = [m] * m left = {} for i in range(m): x = nums[i % n] if x in left: d[i] = min(d[i], i - left[x]) left[x] = i right = {} for i in range(m - 1, - 1, - 1): x = nums[i % n] if x in right: d[i] = min(d[i], right[x] - i) right[x] = i for i in range(n): d[i] = min(d[i], d[i + n]) return [- 1 if d[i] >= n else d[i] for i in queries]

```