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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Absolute Difference Queries

Number: 2034

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array (nums) and an array of queries where each query is represented as [l, r], the task is to compute the minimum absolute difference between any two distinct elements in the subarray nums[l...r]. If the subarray has all elements equal, return -1.

Key Insights

  • The array elements are in the small range [1, 100], which allows us to use precomputation.
  • For each number between 1 and 100, we can store all indices where it appears.
  • For each query, use binary search on the precomputed lists to quickly determine if a number exists in the subarray.
  • Once the available numbers in the subarray are identified, the answer is the minimum difference between consecutive numbers (since they are sorted by their value).

Space and Time Complexity

Time Complexity: O(Q * (R + log(N))) where Q is the number of queries, R is the fixed range (100), and each binary search takes O(log(N)). Overall, this is efficient given the constraints.
Space Complexity: O(N) for storing the indices of numbers.

Solution

The solution precomputes the positions of each number from 1 to 100 using an array/dictionary where each key stores a sorted list of indices where that number appears in nums. For each query [l, r], we iterate from 1 to 100 and use binary search to check if the number occurs in the subarray [l, r]. We then record the candidate numbers that are present and compute the minimum difference between consecutive candidate numbers. If fewer than two distinct numbers are found, the answer for that query is -1.

Code Solutions

import bisect

def min_difference_queries(nums, queries):
    # Precompute positions for each number from 1 to 100.
    positions = {i: [] for i in range(1, 101)}
    for index, num in enumerate(nums):
        positions[num].append(index)
    
    result = []
    # Process each query.
    for l, r in queries:
        prev_candidate = -1
        current_min = float('inf')
        # Check each number in the valid range.
        for num in range(1, 101):
            indices = positions[num]
            if not indices:
                continue
            # Use binary search to check if num exists between l and r.
            pos = bisect.bisect_left(indices, l)
            if pos < len(indices) and indices[pos] <= r:
                if prev_candidate != -1:
                    current_min = min(current_min, num - prev_candidate)
                prev_candidate = num
        result.append(current_min if current_min != float('inf') else -1)
    return result

# Example usage:
nums = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [2, 3], [0, 3]]
print(min_difference_queries(nums, queries))
← Back to All Questions