#1906

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Absolute Difference Queries

Compute minimum absolute differences for subarrays efficiently using array scanning and hash table lookups, leveraging bounded values.

array hash table

Problem Statement

Given an integer array nums and a list of queries where each query is a pair [li, ri], compute the minimum absolute difference for the subarray nums[li..ri]. The minimum absolute difference of an array is the smallest value of |a[i] - a[j]| for 0 <= i < j < a.length with a[i] != a[j], and -1 if all elements are identical.

Return an array of answers where each element corresponds to the minimum absolute difference for the respective query subarray. Arrays are guaranteed to have values between 1 and 100, and each query respects 0 <= li < ri < nums.length.

Examples

Example 1

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]

Output: [2,1,4,1]

The queries are processed as follows:

queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]

Output: [-1,1,1,3]

The queries are processed as follows:

queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the elements are the same.
queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints

2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 104
0 <= li < ri < nums.length

Solution Approach

Hash Table Frequency Count

Use a fixed-size hash table of length 101 to count occurrences of each number in the subarray. Iterate over the table in order to compute minimum absolute differences between consecutive present numbers. This avoids nested comparisons and leverages the bounded value range.

Precompute Prefix Counts

Build a prefix sum of frequency counts for each number in nums. For each query, subtract prefix counts to get the subarray counts quickly. Then, scan the counts to find the minimum absolute difference without iterating over every pair explicitly.

Efficient Query Scanning

Process each query by iterating through only numbers present in the subarray, using the precomputed counts. Compare consecutive numbers to calculate differences. Early exit if the difference 1 is found, since it's the smallest possible, reducing unnecessary checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on whether we precompute prefix counts or scan each query directly. Using prefix counts, each query takes O(100) time, leading to O(queries.length * 100). Space complexity is O(nums.length * 100) if storing prefix frequencies, or O(100) per query without prefix optimization.

What Interviewers Usually Probe

Ask about handling repeated numbers and subarrays with identical elements.
Probe if candidates recognize that maximum nums[i] is 100 and can be used to optimize.
Check if the candidate can reduce O(n^2) comparisons by leveraging hash frequency arrays.

Common Pitfalls or Variants

Common pitfalls

Attempting to compare all pairs in subarrays, leading to timeouts on large arrays.
Forgetting that identical elements result in -1 for the minimum absolute difference.
Ignoring that nums[i] is bounded at 100, missing the optimization opportunity.

Follow-up variants

Compute minimum absolute differences for dynamic updates on nums array.
Handle larger value ranges where hash frequency arrays are impractical.
Find the k-th smallest absolute difference instead of the minimum.

FAQ

What is the main idea behind Minimum Absolute Difference Queries?

It uses array scanning plus hash lookup to compute the smallest difference efficiently without checking all pairs.

Why is the maximum value of 100 important in this problem?

It allows a fixed-size frequency table, so we can iterate counts instead of nested loops, reducing time complexity.

How do you handle queries where all subarray elements are identical?

Return -1 for those queries, since there is no valid pair with different values to compute an absolute difference.

Can this approach handle large numbers of queries efficiently?

Yes, using precomputed prefix frequency arrays, each query is processed in O(100) time, making it scalable.

Is sorting the subarray necessary for this problem?

No, sorting is unnecessary because scanning the fixed-size frequency table in order gives differences in ascending order.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        m, n = len(nums), len(queries)
        pre_sum = [[0] * 101 for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, 101):
                t = 1 if nums[i - 1] == j else 0
                pre_sum[i][j] = pre_sum[i - 1][j] + t

        ans = []
        for i in range(n):
            left, right = queries[i][0], queries[i][1] + 1
            t = inf
            last = -1
            for j in range(1, 101):
                if pre_sum[right][j] - pre_sum[left][j] > 0:
                    if last != -1:
                        t = min(t, j - last)
                    last = j
            if t == inf:
                t = -1
            ans.append(t)
        return ans

Continue Practicing

#1912 design movie rental system #1893 check if all the integers in a range are covered #1938 maximum genetic difference query