How do you solve Closest Equal Element Queries on LeetCode?

Closest Equal Element Queries (LeetCode #3488) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m log k) time complexity and O(n) space complexity. Key insight: Using a dictionary for index mapping speeds up lookups.

What is the time complexity of Closest Equal Element Queries?

The optimal solution for Closest Equal Element Queries runs in O(n + m log k) time and uses O(n) space. Building the index map takes O(n), and each query takes O(log k) for binary search on k indices.

What is the brute force solution for Closest Equal Element Queries?

The brute force approach for Closest Equal Element Queries is Brute Force, with O(n²) time complexity and O(1) space complexity. Check every index for each query to find the closest equal element. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n + m log k).

What algorithm or data structure is used to solve Closest Equal Element Queries?

Closest Equal Element Queries uses the following concepts: Array, Hash Table, Binary Search. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Closest Equal Element Queries?

Explain your thought process clearly. Discuss edge cases and how your solution handles them. Practice coding on a whiteboard or in an online editor.

What are common mistakes when solving Closest Equal Element Queries?

Not considering the circular nature of the array. Failing to handle cases where no equal elements exist.

#3488

Closest Equal Element Queries

Medium

ArrayHash TableBinary SearchHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + m log k)
Space	O(1)	O(n)

💡

Intuition

Time O(n + m log k)Space O(n)

Use a dictionary to map values to their indices, allowing efficient lookups and circular distance calculations.

⚙️

Algorithm

3 steps

1Step 1: Create a dictionary mapping each unique value in nums to a sorted list of its indices.
2Step 2: For each query, use binary search to find the closest indices of the target value.
3Step 3: Calculate the circular distance and return the minimum distance.

solution.py21 lines

1def closestEqual(nums, queries):
2    from collections import defaultdict
3    import bisect
4    index_map = defaultdict(list)
5    for i, num in enumerate(nums):
6        index_map[num].append(i)
7    result = []
8    n = len(nums)
9    for q in queries:
10        target = nums[q]
11        indices = index_map[target]
12        if len(indices) < 2:
13            result.append(-1)
14            continue
15        pos = bisect.bisect_left(indices, q)
16        min_dist = float('inf')
17        for idx in [indices[pos % len(indices)], indices[(pos - 1) % len(indices)]]:
18            dist = min(abs(idx - q), n - abs(idx - q))
19            min_dist = min(min_dist, dist)
20        result.append(min_dist)
21    return result

ℹ

Complexity note: Building the index map takes O(n), and each query takes O(log k) for binary search on k indices.

1Using a dictionary for index mapping speeds up lookups.
2Circular distance calculations can be efficiently handled with modulo operations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.