Skip to main content
Talentd

Closest Equal Element Queries - Solution & Explanation

MediumArrayHash TableBinary Search12 min readAsked at: Amazon, Salesforce, Google +1
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * q)O(1)Small arrays or when implementing the simplest baseline
Hash Table + Binary Search on Index ListsO((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

Video Solution

Closest Equal Element Queries | Super Simplified | Dry Run | Leetcode 3488 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 6,946 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Closest Equal Element Queries easy or hard?
Closest Equal Element Queries is generally rated Medium difficulty. The challenge is recognizing that scanning the array per query is too slow and switching to a preprocessing strategy using hash maps and binary search.
Closest Equal Element Queries Python/Java solution
The standard implementation builds a dictionary or HashMap from value to index list. For each query, locate the position using binary search and compare distances to adjacent indices while accounting for circular wrap-around. The same logic works in Python, Java, C++, Go, and other languages.
How to solve Closest Equal Element Queries in O(n)?
Preprocess the array by storing all indices of each value in a hash map. For every query, perform a binary search in the list of indices for that value and check the nearest previous and next positions. Because the array is circular, compute distance using min(|iāˆ’j|, nāˆ’|iāˆ’j|). This reduces repeated scanning and keeps queries fast.
What is the best approach for Closest Equal Element Queries?
The most efficient approach groups indices of the same value using a hash table, then answers each query with binary search on the index list. Only the nearest neighbors in that list need to be checked. This reduces repeated scanning and handles the circular distance efficiently. The overall complexity is O((n + q) log n) time and O(n) space.
Is Closest Equal Element Queries asked at Google/Amazon/Meta?
Problems involving nearest equal elements, circular arrays, and hash map indexing appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test preprocessing with hash maps and efficient query handling using binary search or pointer techniques.
What data structure is used in Closest Equal Element Queries?
The key data structure is a hash table that maps each value to a sorted list of its indices in the array. Binary search is then applied on these lists to locate the closest neighboring occurrences for a queried index.
What is the time complexity of Closest Equal Element Queries?
The optimal solution runs in O((n + q) log n) time. Building the hash table of value ā†’ indices takes O(n). Each query performs a binary search on the occurrence list of that value, which costs O(log n) in the worst case.

Ready to solve this problem?

Practice Closest Equal Element Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays