LeetCode 1906 - Minimum Absolute Difference Queries

The problem asks us to compute the minimum absolute difference in subarrays of a given integer array nums for multiple q

leetcodemediumarrayprefix-sum

LeetCode Problem 1906

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to compute the minimum absolute difference in subarrays of a given integer array nums for multiple queries. Each query specifies a subarray with indices [li, ri], and we need to find the smallest difference between any two distinct elements in that subarray. If all elements in the subarray are identical, the minimum absolute difference is -1.

The input consists of an array nums with values between 1 and 100, and a list of queries where each query is a pair of indices [li, ri]. The constraints indicate that nums can be up to 10^5 elements long, and there can be up to 2 * 10^4 queries. A naive approach that directly checks every pair in each query would be too slow, because it could require up to $O(n^2)$ operations per query, which is infeasible for large inputs.

Important edge cases include subarrays where all elements are identical (which must return -1), subarrays of size 2 (which only have one difference to compute), and queries that span the entire array.

Approaches

The brute-force approach is straightforward: for each query, extract the subarray, sort it, and compute the minimum difference by iterating through consecutive elements. Sorting ensures that differences between consecutive elements are sufficient to find the minimum, since the minimum absolute difference must occur between adjacent numbers when sorted. This works correctly, but sorting each subarray per query results in a time complexity of $O(q \cdot m \log m)$, where $m$ is the length of the subarray, which is too slow for large input sizes.

The optimal approach leverages the constraints that 1 <= nums[i] <= 100. Because the values are small, we can use prefix frequency arrays to quickly know which numbers appear in any subarray. We build a 2D prefix sum array prefix[i][num] where prefix[i][num] indicates how many times num appears from index 0 to i. Then for a query [li, ri], we can efficiently determine which numbers are present in the subarray, iterate over the present numbers in order, and compute the minimum difference. This reduces the per-query time to $O(100) = O(1)$ and makes the algorithm feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(q * m log m) O(m) Sort each subarray per query, too slow for large n or many queries
Optimal O(n * 100 + q * 100) O(n * 100) Uses prefix frequency arrays to check numbers efficiently

Algorithm Walkthrough

  1. Initialize a 2D prefix array prefix of size (n+1) x 101 filled with zeros. prefix[i][num] will count occurrences of num up to index i-1 in nums.
  2. Populate the prefix array by iterating over nums. For each index i, copy counts from prefix[i] to prefix[i+1], and increment the count for nums[i].
  3. For each query [li, ri], determine which numbers exist in the subarray by computing prefix[ri+1][num] - prefix[li][num]. If the difference is greater than 0, the number exists in the subarray.
  4. Iterate over numbers 1 through 100 and track the previous number seen. Compute the difference between consecutive numbers and update the minimum difference found.
  5. If fewer than 2 distinct numbers exist in the subarray, return -1. Otherwise, return the computed minimum difference.

Why it works: The prefix frequency array guarantees that we can determine the presence of any number in a subarray in O(1) time. Since the range of numbers is limited to 1-100, iterating through all possible numbers is fast. By checking consecutive numbers, we ensure that the smallest possible absolute difference is found.

Python Solution

from typing import List

class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        # Step 1: Build prefix frequency array
        prefix = [[0] * 101 for _ in range(n + 1)]
        for i in range(n):
            for num in range(1, 101):
                prefix[i + 1][num] = prefix[i][num]
            prefix[i + 1][nums[i]] += 1
        
        res = []
        for li, ri in queries:
            # Step 2: Find numbers present in subarray
            present = [num for num in range(1, 101) if prefix[ri + 1][num] - prefix[li][num] > 0]
            
            if len(present) < 2:
                res.append(-1)
            else:
                min_diff = float('inf')
                for i in range(1, len(present)):
                    min_diff = min(min_diff, present[i] - present[i - 1])
                res.append(min_diff)
        return res

Explanation: We first construct the prefix frequency array to efficiently determine which numbers are present in any subarray. For each query, we build a list of numbers that occur in the subarray, then compute the minimum difference between consecutive numbers. If there are fewer than 2 distinct numbers, we return -1.

Go Solution

func minDifference(nums []int, queries [][]int) []int {
    n := len(nums)
    prefix := make([][101]int, n+1)
    
    for i := 0; i < n; i++ {
        for num := 1; num <= 100; num++ {
            prefix[i+1][num] = prefix[i][num]
        }
        prefix[i+1][nums[i]]++
    }
    
    res := make([]int, len(queries))
    for q, query := range queries {
        li, ri := query[0], query[1]
        present := make([]int, 0)
        for num := 1; num <= 100; num++ {
            if prefix[ri+1][num]-prefix[li][num] > 0 {
                present = append(present, num)
            }
        }
        
        if len(present) < 2 {
            res[q] = -1
        } else {
            minDiff := 101
            for i := 1; i < len(present); i++ {
                diff := present[i] - present[i-1]
                if diff < minDiff {
                    minDiff = diff
                }
            }
            res[q] = minDiff
        }
    }
    return res
}

Go-specific notes: The main difference from Python is using fixed-size arrays [101]int for the prefix sums, and slice operations for the present numbers. Go requires careful initialization of arrays to avoid nil slices, which is handled here.

Worked Examples

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

Query Subarray Present Numbers Min Diff
[0,1] [1,3] [1,3] 2
[1,2] [3,4] [3,4] 1
[2,3] [4,8] [4,8] 4
[0,3] [1,3,4,8] [1,3,4,8] 1

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

Query Subarray Present Numbers Min Diff
[2,3] [2,2] [2] -1
[0,2] [4,5,2] [2,4,5] 1
[0,5] [4,5,2,2,7,10] [2,4,5,7,10] 1
[3,5] [2,7,10] [2,7,10] 3

Complexity Analysis

Measure Complexity Explanation
Time O(n * 100 + q * 100) Building prefix array takes O(n * 100), each query checks up to 100 numbers
Space O(n * 100) Storing prefix frequency array

The algorithm is efficient because the values of nums[i] are bounded by 100, so iterating over all possible values is effectively constant time per query.

Test Cases

# Example tests
assert Solution().minDifference([1,3,4,8], [[0,1],[1,2],[2,3],[0,3]]) == [2,1,4,1]  # standard case
assert Solution().minDifference([4,5,2,2,7,10], [[2,3],[0,2],[0,5],[3,5