You are given a circular array nums and an array queries.
For each query i, you have to find the following:
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:
queries[0] = 0 is nums[0] = 1. The nearest index with the same value is 2, and the distance between them is 2.queries[1] = 3 is nums[3] = 4. No other index contains 4, so the result is -1.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 <= 1051 <= nums[i] <= 1060 <= queries[i] < nums.lengthProblem Overview: You are given an array and several queries. For each queried index, return the distance to the nearest index containing the same value. The array is treated as circular, so moving past the last element wraps back to the start. If no other equal element exists, return -1.
Approach 1: Brute Force Scan (O(n * q) time, O(1) space)
For every query index i, scan the entire array and look for other indices where nums[j] == nums[i]. Compute the circular distance using min(|i-j|, n-|i-j|). Track the smallest distance across all matches. This approach uses only the array itself and requires no preprocessing, but it becomes slow when both n and the number of queries are large. Each query may traverse the full array, leading to O(n) work per query.
Approach 2: Circular Array + Hash Table + Binary Search (O((n + q) log n) time, O(n) space)
Store every index of each value in a hash table: value → sorted list of indices. Because you process the array from left to right, these lists are already sorted. For a query index i, fetch the list corresponding to nums[i]. If the list has only one index, no equal element exists and the answer is -1.
Otherwise, use binary search to find the position of i inside that index list. The closest candidates must be the previous and next occurrences in the list. Compute distances to both neighbors. Since the array is circular, also consider wrapping from the first index to the last. The final answer is the minimum circular distance among these candidates.
This preprocessing converts repeated scans into fast lookups. Each query touches only the occurrence list for that value and performs a binary search, making it efficient even when the number of queries is large.
Recommended for interviews: The hash table + binary search method is the expected solution. The brute force version shows you understand the distance definition and circular behavior, but it does not scale. Interviewers typically want to see you group indices by value using a hash map and then narrow the search with binary search. That combination demonstrates practical use of arrays, indexing strategies, and query optimization.
According to the problem description, we need to find the minimum distance between each element in the array and its previous identical element, as well as the minimum distance to its next identical element. Since the array is circular, we need to consider the circular nature of the array. We can extend the array to twice its original length, and then use hash tables left and right to record the positions where each element last appeared and will next appear, respectively. We calculate the minimum distance between each position's element and another identical element, recording it in the array d. Finally, we traverse the queries, and for each query i, we take the minimum value of d[i] and d[i+n]. If this value is greater than or equal to n, it means there is no element identical to the queried element, so we return -1; otherwise, we return the value.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * q) | O(1) | Small arrays or when implementing the simplest baseline |
| Hash Table + Binary Search on Index Lists | O((n + q) log n) | O(n) | General case with many queries; efficient lookups per value |
| Circular Index Neighbor Check (optimized lists) | O(n + q log k) | O(n) | Best when values repeat frequently and occurrence lists are small |
3488 Closest Equal Element Queries | LeetCode • R Sai Siddhu • 1,214 views views
Watch 5 more video solutions →Practice Closest Equal Element Queries with our built-in code editor and test cases.
Practice on FleetCode