#3488

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Closest Equal Element Queries

Find the nearest index with the same value for each query using array scanning combined with hash lookups efficiently.

Problem Statement

You are given a circular array nums and an array of queries. For each query index, you need to identify the nearest index where the value equals nums[query], considering circular wrapping.

Return an array answer where answer[i] represents the closest index with the same value as nums[queries[i]]. If no such index exists, return -1 for that query. The array should handle large inputs efficiently using hash-based indexing and ordered scans.

Examples

Example 1

Input: nums = [1,3,1,4,1,3,2], queries = [0,3,5]

Output: [2,-1,3]

Example 2

Input: nums = [1,2,3,4], queries = [0,1,2,3]

Output: [-1,-1,-1,-1]

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

Solution Approach

Preprocess with a Hash Map of Indices

Create a dictionary mapping each unique value in nums to a sorted list of all indices where it occurs. This allows quick access to candidate indices for any query value without scanning the entire array each time.

Binary Search for Nearest Index

For each query, perform a binary search on the sorted list of indices for nums[query] to find the closest index. Consider circular wrapping by comparing distance from both lower and higher neighboring indices.

Assemble Results Efficiently

Iterate over all queries, applying the preprocessed hash map and binary search to compute answer[i]. Store -1 if no alternative index exists. This approach minimizes redundant scanning and leverages the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N + Q log K) where N is the length of nums, Q is the number of queries, and K is the frequency of the queried value. Space complexity is O(N) for the hash map storing indices.

What Interviewers Usually Probe

Looking for hash-based preprocessing to avoid repeated full scans.
Checking understanding of circular array indexing and nearest distance calculation.
Expecting efficient O(log K) lookup per query instead of naive O(N) search.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle circular array wrapping when computing distances.
Scanning the entire array for each query, leading to timeouts on large inputs.
Neglecting to sort indices in the hash map, making binary search incorrect.

Follow-up variants

Non-circular version where array ends are not connected, simplifying distance calculation.
Queries that ask for the farthest matching index instead of the closest.
Dynamic updates to nums where indices mapping must be maintained after each change.

FAQ

What pattern does Closest Equal Element Queries follow?

It follows the array scanning plus hash lookup pattern, combining dictionary-based preprocessing with efficient nearest index search.

How do I handle circular wrapping in the array?

Compare distances both forward and backward in the circular sense, using modulo arithmetic to wrap around the array ends.

Why is a sorted list of indices needed?

Sorting allows binary search to quickly find the nearest index, reducing query processing from O(N) to O(log K).

What should I return if no matching index exists?

Return -1 for that query to indicate no other index shares the same value.

Can this approach handle large arrays efficiently?

Yes, preprocessing with a hash map and binary search ensures the solution scales to arrays of length up to 10^5.

terminal

Solution

Solution 1: Circular Array + Hash Table

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 $\textit{left}$ and $\textit{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 $\textit{d}$. Finally, we traverse the queries, and for each query $i$, we take the minimum value of $\textit{d}[i]$ and $\textit{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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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]

Continue Practicing

#3508 implement router #3532 path existence queries in a graph i #3312 sorted gcd pair queries