We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Equal Element Queries

Difficulty: Medium

Problem Description

You are given a circular array nums and an array queries. For each query i, you have to find 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.

Key Insights

  • The problem involves a circular array, which means that the end of the array wraps around to the beginning.
  • We need to find the nearest index with the same value for multiple queries efficiently.
  • Using a hash table can help store the indices of each element in the array, allowing for quick lookups.
  • The distance calculation must consider the circular nature of the array.

Space and Time Complexity

Time Complexity: O(n + q), where n is the length of nums and q is the length of queries
Space Complexity: O(n), for storing indices in the hash table.

Solution

To solve this problem, we can use a hash table to map each unique element in the nums array to a list of its indices. For each query, we can then check this list to find the nearest index with the same value. The distance is calculated by considering both the direct distance and the circular distance.

  1. Create a hash table where the key is the element and the value is a list of indices where this element occurs.
  2. For each query, retrieve the list of indices for the queried element.
  3. If the list contains only the index from the query, return -1.
  4. Otherwise, calculate the minimum distance using both the direct and circular distances.

Code Solutions

def closestEqualElementQueries(nums, queries):
    from collections import defaultdict
    
    # Step 1: Create a hash table to store indices of each element
    index_map = defaultdict(list)
    n = len(nums)
    
    for idx, num in enumerate(nums):
        index_map[num].append(idx)
    
    # Step 2: Prepare the result array
    result = []
    
    for query in queries:
        value = nums[query]
        indices = index_map[value]
        
        # If there's only one index, return -1
        if len(indices) <= 1:
            result.append(-1)
            continue
        
        # Step 3: Calculate the minimum distance
        min_distance = float('inf')
        
        for idx in indices:
            if idx != query:
                direct_distance = abs(idx - query)
                circular_distance = n - direct_distance
                min_distance = min(min_distance, direct_distance, circular_distance)
        
        result.append(min_distance)
    
    return result
← Back to All Questions