Minimum Absolute Difference Queries: Prefix Counts on Small Domains

You are given an integer array nums and a list of queries. Each query gives you a range [li, ri], and you need to find the minimum absolute difference between any two elements in the subarray nums[li..ri]. If every element in the subarray is the same, return -1. This is LeetCode 1906: Minimum Absolute Difference Queries, and the trick to solving it efficiently is hiding in a constraint you might overlook: all values are in the range [1, 100].

Why this problem matters

This problem teaches you how to exploit a small value domain. When the set of possible values is bounded by a constant, you can precompute frequency information and answer range queries in constant time per value. That idea shows up in many competitive programming problems and system design scenarios (think histograms, frequency tables, and range-based analytics).

It also reinforces the prefix sum technique, but applied to frequency counts rather than raw values. If you are comfortable with standard prefix sums, this problem extends that same concept into a higher dimension.

The key insight: prefix frequency counts

The constraint 1 <= nums[i] <= 100 is the entire key. There are at most 100 distinct values. For each value v, you can build a prefix count array: prefix[i][v] stores how many times v appears in nums[0..i-1].

With that table precomputed, answering any query [l, r] becomes a scan through all 100 possible values. For each value v, the count in the subarray is prefix[r+1][v] - prefix[l][v]. If that count is positive, the value is present. You collect the present values in sorted order (since you scan from 1 to 100), then compute the minimum gap between consecutive present values.

The approach

1. Build prefix counts. Create a 2D array where prefix[i][v] is the number of times value v appears in nums[0..i-1]. Fill it by iterating through nums once.

2. Answer each query. For a query [l, r], scan values 1 through 100. For each value, compute prefix[r+1][v] - prefix[l][v]. If positive, the value is present. Track the previous present value and update the minimum gap.

3. Handle the edge case. If only one distinct value (or zero) is present, return -1 for that query.

def min_absolute_difference(nums, queries):
    n = len(nums)
    V = 101

    prefix = [[0] * V for _ in range(n + 1)]
    for i in range(n):
        for v in range(V):
            prefix[i + 1][v] = prefix[i][v]
        prefix[i + 1][nums[i]] += 1

    result = []
    for l, r in queries:
        min_diff = float('inf')
        prev = -1
        for v in range(1, V):
            if prefix[r + 1][v] - prefix[l][v] > 0:
                if prev != -1:
                    min_diff = min(min_diff, v - prev)
                prev = v
        result.append(min_diff if min_diff != float('inf') else -1)

    return result

Complexity analysis

Where V = 100 (the value range).

The prefix count approach is efficient because V is a constant. Building the table costs O(n * V), and each query costs O(V). With up to 100,000 queries and n up to 100,000, the total work is around 20 million operations, well within time limits.

Building blocks

This problem uses two fundamental patterns:

• Prefix sums. The same idea behind range sum queries. Instead of summing values, you are summing frequencies. If you know how to compute prefix[r+1] - prefix[l] for a 1D prefix sum, the extension to per-value prefix counts is natural.
• Frequency counting over a bounded domain. When values fit in a small range, you can use arrays instead of hash maps. Iterating over the domain in order gives you sorted access for free, which is exactly what you need to find minimum gaps.

Edge cases

• All elements the same in a subarray. Only one value is present, so there is no pair to compare. Return -1.
• Subarray of length 1. Only one element, no pair exists. Return -1. (Note: the problem guarantees li < ri in valid queries, but the logic handles this naturally.)
• Two adjacent values present. The minimum possible gap is 1. Once you find a gap of 1, you can short-circuit and stop scanning for that query.
• All 100 values present. You still scan 100 values, compute 99 gaps, and return the minimum. The work is bounded by the constant V.

From understanding to recall

You can follow each step of the prefix count technique in the diagrams above. But will you remember to reach for this approach when you see a range query problem with bounded values? The gap between understanding a technique and recognizing when to apply it is real. Spaced repetition bridges that gap. You revisit this pattern at increasing intervals, each time rebuilding the mental connection between "small value domain" and "prefix frequency arrays." After a few reps, the connection becomes automatic.

Related posts

• Contains Duplicate - frequency counting fundamentals
• Group Anagrams - another problem where value-domain constraints enable efficient solutions
• Daily Temperatures - range-based reasoning over arrays