Watch 6 video solutions for Closest Equal Element Queries, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by R Sai Siddhu has 1,214 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |