LeetCode Solutions Blog

Closest Equal Element Queries

Number: 3750

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a circular array called nums and a list of queries, for each query index, find the minimum circular distance from the queried index to any other index with the same value. If no such index exists, return -1 for that query.

Key Insights

Preprocess the input array to map each value to the list of all indices where that value occurs.
Since the array is circular, the distance between two indices requires considering wrapping around the end of the array.
Use binary search on each sorted list of indices when processing a query to quickly find the nearest indices with the same value.
Consider both the right (or forward) and left (or backward) neighbors and compute the appropriate circular distances.

Space and Time Complexity

Time Complexity: O(n + q * log(n))
Space Complexity: O(n)

Solution

To solve the problem efficiently:

Traverse the nums array once to build a dictionary mapping each unique value to a sorted list of its indices.
For each query, retrieve the list of indices for the target value.
If the list contains just one element, return -1.
Use binary search to determine the position of the queried index within the list.
Identify the potential nearest neighbor indices (one immediately before and one immediately after the queried index in the circular sense).
Calculate the circular distances by taking into account the possibility of wrapping around the array boundaries.
Return the minimum of these distances.

The main trick is handling the circular nature by also checking the wrap-around candidate (i.e., the difference between the queried index and the first or last index in the list, considering the circular gap).

Code Solutions

# Python solution for the Closest Equal Element Queries problem

import bisect

def closestEqualDistance(nums, queries):
    n = len(nums)
    # Build a dictionary that maps values to all their indices in nums
    indices_map = {}
    for i, num in enumerate(nums):
        if num not in indices_map:
            indices_map[num] = []
        indices_map[num].append(i)
    
    result = []
    
    # Process each query
    for query in queries:
        target_value = nums[query]
        positions = indices_map[target_value]
        
        # If the target value occurs only once, no valid pair exists.
        if len(positions) == 1:
            result.append(-1)
            continue
        
        # Use binary search to find the insertion point for query in positions
        pos = bisect.bisect_left(positions, query)
        
        # Determine the indices for both the right neighbor and the left neighbor in circular order
        right_idx = positions[pos % len(positions)]
        left_idx = positions[pos - 1]  # pos - 1 is always valid because len(positions) >= 2
        
        # Calculate circular distances:
        # Distance going right (if right_idx is before query, it means wrap-around)
        if right_idx >= query:
            right_distance = right_idx - query
        else:
            right_distance = n - query + right_idx
        
        # Distance going left (if query is less than left_idx, then wrap-around is required)
        if query >= left_idx:
            left_distance = query - left_idx
        else:
            left_distance = query + n - left_idx
        
        # The answer is the minimal distance from the two directions
        result.append(min(right_distance, left_distance))
    
    return result

# Example usage:
nums = [1,3,1,4,1,3,2]
queries = [0,3,5]
print(closestEqualDistance(nums, queries))  # Output: [2,-1,3]