3488. Closest Equal Element Queries

3488. Closest Equal Element Queries

Difficulty: Medium

Topics: Senior, Array, Hash Table, Binary Search, Weekly Contest 441

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.

Example 3:

• Input: nums = [5,5,5,1,2,5], queries = [0,3,5]
• Output: [1, -1, 1]

Constraints:

• 1 <= queries.length <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁶
• 0 <= queries[i] < nums.length

Hint:

1. Use a dictionary that maps each unique value in the array to a sorted list of its indices.
2. For each query, use binary search on the sorted indices list to find the nearest occurrences of the target value.

Solution:

The problem asks for the minimum circular distance between a given index and any other index containing the same value.

The solution groups indices by value, uses binary search to find neighbors in the circular array, and computes distances with wrap-around logic.

If a value appears only once, the answer is -1.

Approach:

• Group indices by value using a hash map (dictionary) where keys are array values and values are sorted lists of their indices.
• For each query index:
  • Retrieve the sorted list of indices for its value.
  • If only one index exists → answer is -1.
  • Use binary search to locate the query index within its value’s index list.
  • Check the previous and next indices in the circular list (wrap around using modulo).
  • Compute the circular distance between the query index and each candidate.
  • Take the minimum of these distances as the answer.
• Return an array of answers in the same order as queries.

Let's implement this solution in PHP: 3488. Closest Equal Element Queries

<?php
/**
 * @param Integer[] $nums
 * @param Integer[] $queries
 * @return Integer[]
 */
function solveQueries(array $nums, array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Binary search to find the exact position or insertion point
 *
 * @param $arr
 * @param $target
 * @return mixed
 */
function binarySearch($arr, $target): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Calculate circular distance between two indices
 *
 * @param $i
 * @param $j
 * @param $n
 * @return mixed
 */
function circularDistance($i, $j, $n): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo solveQueries([1,3,1,4,1,3,2], [0,3,5]) . "\n";         // Output: [2,-1,3]
echo solveQueries([1,2,3,4], [0,1,2,3]) . "\n";             // Output: [-1,-1,-1,-1]
echo solveQueries([5,5,5,1,2,5], [0,3,5]) . "\n";           // Output: [1, -1, 1]

?>

Explanation:

• Grouping indices: We traverse the array once and store each index in a list corresponding to its value. This allows quick access to all positions of a given value.
• Binary search for neighbors: For a query index q, we find its position in the sorted index list. Then, the nearest other indices with the same value are the ones immediately before and after it in that list (wrapping around at ends).
• Circular distance: On a circular array of length n, the distance between indices i and j is min(|i - j|, n - |i - j|).
• Handling uniqueness: If a value appears only once, there is no other index to compare, so we return -1.

Complexity

• Time Complexity:
  • Grouping indices: O(n)
  • Each query: binary search O(log m) where m is the frequency of that value
  • Total: O(n + q log n) worst case, but since q ≤ n, it’s efficient.
• Space Complexity: Hash map storing all indices: O(n)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub