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

Minimum Absolute Difference Queries

Difficulty: Medium

Problem Description

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1. You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive). Return an array ans where ans[i] is the answer to the ith query.

Key Insights

  • We need to find the minimum absolute difference between distinct elements in specified subarrays.
  • If a subarray contains all identical elements, the answer is -1.
  • Efficiently handling multiple queries requires an approach that can quickly compute results without re-evaluating the entire subarray for each query.
  • The elements in nums are constrained between 1 and 100, allowing for effective frequency counting.

Space and Time Complexity

Time Complexity: O(q * k) where q is the number of queries and k is the maximum length of the subarray for any query. This can be optimized to O(n log n) for preprocessing. Space Complexity: O(1) for the frequency array (due to the bounded range of values in nums).

Solution

To solve this problem, we can utilize a frequency array to count occurrences of each number in the subarray. By iterating through the frequency array, we can find the smallest difference between distinct elements. If the maximum frequency is equal to the length of the subarray, then all elements are identical, and we return -1.

  1. For each query, extract the relevant subarray.
  2. Build a frequency array to count occurrences of each number in the range.
  3. Determine the minimum absolute difference by iterating through the frequency array.

Code Solutions

def min_absolute_difference(nums, queries):
    results = []
    for l, r in queries:
        freq = [0] * 101  # Since nums[i] is between 1 and 100
        for i in range(l, r + 1):
            freq[nums[i]] += 1
        
        last_num = -1
        min_diff = float('inf')
        for num in range(1, 101):
            if freq[num] > 0:
                if last_num != -1:
                    min_diff = min(min_diff, num - last_num)
                last_num = num
        
        results.append(min_diff if min_diff != float('inf') else -1)
    
    return results
← Back to All Questions