Closest Equal Element Queries — Problem & Solution
Closest Equal Element Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Closest Equal Element Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a circular array nums (the element after the last one is the first one) and an array queries of indices into it.
For each query index i, find the minimum distance from i to any other index j with nums[j] == nums[i]. Distances are measured around the circle: between i and j it is min(|i - j|, n - |i - j|). If no other index holds the same value, the answer is -1.
Return the answers in the order of queries.
Example 1
Input: nums = [5,2,5,7,2,5], queries = [0,3,4]
Output: [1,-1,3]
Explanation: Index 0 reaches the `5` at index 5 by wrapping around (distance 1). `7` occurs once. The other `2` is 3 steps away either way.
Example 2
Input: nums = [1,2,3,4], queries = [0,1,2,3]
Output: [-1,-1,-1,-1]
Explanation: Every value is unique.
Example 3
Input: nums = [8,8], queries = [1]
Output: [1]
Constraints
1 <= queries.length <= nums.length <= 10^51 <= nums[i] <= 10^60 <= queries[i] < nums.length
Hints for Closest Equal Element Queries
Hint 1
Group the indices by value. Inside one group, which other index can be closest to a given index on the circle?
Hint 2
Sort each group's indices. The closest equal element is always one of the two neighbours in that sorted list — treating the list itself as circular, so the first and last indices are neighbours too.
Hint 3
Precompute the answer for every index once (
-1for groups of size 1), then answer each query by lookup.
How to solve Closest Equal Element Queries
On a circle, the nearest index holding the same value is the next or previous occurrence of that value going around. Listing each value's indices in increasing order makes those two occurrences neighbours in the list, with wrap-around.
Approach
- Collect, for each value, the list of indices where it occurs (in increasing order).
- For a list of size 1, its index answers
-1. - For a list
idxof sizem >= 2, eachidx[t]answers the smaller circular distance toidx[t - 1]andidx[t + 1], indices taken modulom. - Return
answer[queries[k]]for each query.
Why it works
Walking clockwise from i, the first equal value met is the next occurrence in sorted order (or the first one, after wrapping). Walking counter-clockwise it is the previous occurrence. The circular distance to any other occurrence is at least the walk to one of these two, because reaching it requires passing one of them first in the direction of the shorter arc.
Complexity
- Time —
O(n log n) with sorting, or O(n) with a hash map filled left to right - Space —
O(n)
Pitfalls
- Forgetting the wrap-around neighbour: the first and last occurrences can be adjacent across the end of the array.
- The distance itself is also circular: take
min(d, n - d). - Answering each query by scanning the array is
O(n * q)— too slow at10^5.
Reference solution
Python
from typing import List
def solveQueries(nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
groups = {}
for i, v in enumerate(nums):
groups.setdefault(v, []).append(i)
best = [-1] * n
for idx in groups.values():
m = len(idx)
if m < 2:
continue
for t in range(m):
i = idx[t]
for j in (idx[t - 1], idx[(t + 1) % m]):
d = abs(i - j)
d = min(d, n - d)
if best[i] < 0 or d < best[i]:
best[i] = d
return [best[q] for q in queries]Java
public static int[] solveQueries(int[] nums, int[] queries) {
int n = nums.length;
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(nums[i], x -> new ArrayList<>()).add(i);
int[] best = new int[n];
Arrays.fill(best, -1);
for (List<Integer> idx : groups.values()) {
int m = idx.size();
if (m < 2) continue;
for (int t = 0; t < m; t++) {
int a = idx.get(t);
int[] nb = { idx.get((t - 1 + m) % m), idx.get((t + 1) % m) };
for (int j : nb) {
int d = Math.abs(a - j);
d = Math.min(d, n - d);
if (best[a] < 0 || d < best[a]) best[a] = d;
}
}
}
int[] out = new int[queries.length];
for (int q = 0; q < queries.length; q++) out[q] = best[queries[q]];
return out;
}C++
vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
int n = nums.size();
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[nums[i]].push_back(i);
vector<int> best(n, -1);
for (auto& kv : groups) {
vector<int>& idx = kv.second;
int m = idx.size();
if (m < 2) continue;
for (int t = 0; t < m; t++) {
int a = idx[t];
int nb[2] = { idx[(t - 1 + m) % m], idx[(t + 1) % m] };
for (int j : nb) {
int d = abs(a - j);
d = min(d, n - d);
if (best[a] < 0 || d < best[a]) best[a] = d;
}
}
}
vector<int> out;
for (int q : queries) out.push_back(best[q]);
return out;
}JavaScript
var solveQueries = function(nums, queries) {
var n = nums.length;
var groups = new Map();
for (var i = 0; i < n; i++) {
var g = groups.get(nums[i]);
if (!g) { g = []; groups.set(nums[i], g); }
g.push(i);
}
var best = new Array(n).fill(-1);
groups.forEach(function(idx) {
var m = idx.length;
if (m < 2) return;
for (var t = 0; t < m; t++) {
var a = idx[t];
var nb = [idx[(t - 1 + m) % m], idx[(t + 1) % m]];
for (var k = 0; k < 2; k++) {
var d = Math.abs(a - nb[k]);
d = Math.min(d, n - d);
if (best[a] < 0 || d < best[a]) best[a] = d;
}
}
});
var out = [];
for (var q = 0; q < queries.length; q++) out.push(best[queries[q]]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets