Problem Description

The Minimum Absolute Difference Queries problem provides you with an array of positive integers nums (with values in the range [1, 100]) and a list of queries, where each query is a pair of indices [l, r]. For each query, you must find the minimum absolute difference between any two distinct elements in the subarray nums[l..r].

• If there is only one distinct value in the subarray, return -1 for that query.
• You must process all queries efficiently, given that both nums and queries can be large.
• Elements can be reused within the subarray, but the minimum absolute difference must be between two different elements.

The goal is to return a list of integers, each representing the answer for the corresponding query.

Thought Process

At first, it seems natural to process each query independently: for each subarray defined by [l, r], extract the elements, find all pairs, and compute their absolute differences. However, this brute-force approach is inefficient, especially for large inputs, since there could be up to O(n^2) pairs per query.

To optimize, notice that:

• Values are limited to [1, 100], so the number of distinct possible values in any subarray is small.
• We can precompute information to quickly determine which values are present in any subarray.
• For each query, if we know which values are present, we can sort them and the minimum absolute difference will be between adjacent values.

Solution Approach

Here’s how we solve the problem efficiently:

1. Build Prefix Sums for Each Value:
   • For each possible value (1 to 100), construct a prefix sum array indicating how many times that value has appeared up to each index in nums.
   • This allows us to quickly determine if a value exists in any subarray nums[l..r] by checking if the count increased.
2. Process Each Query:
   • For a query [l, r], for each value from 1 to 100, check if it appears in the subarray using the prefix sums.
   • Collect all present values into a list, then sort this list.
   • If there is only one value, return -1 (no pairs exist).
   • Otherwise, compute the minimum difference between adjacent values in the sorted list.
3. Output:
   • Return the computed minimum absolute difference for each query in order.

This approach is efficient because we avoid recomputation and use the constraints to our advantage.

Example Walkthrough

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

1. Query [0, 2]:
   • Subarray: [1, 3, 4]
   • Distinct values: 1, 3, 4
   • Sorted: [1, 3, 4]
   • Differences: |3-1|=2, |4-3|=1
   • Minimum: 1
2. Query [1, 4]:
   • Subarray: [3, 4, 8, 6]
   • Distinct values: 3, 4, 6, 8
   • Sorted: [3, 4, 6, 8]
   • Differences: |4-3|=1, |6-4|=2, |8-6|=2
   • Minimum: 1
3. Query [2, 4]:
   • Subarray: [4, 8, 6]
   • Distinct values: 4, 6, 8
   • Sorted: [4, 6, 8]
   • Differences: |6-4|=2, |8-6|=2
   • Minimum: 2

The final result is [1, 1, 2].

Time and Space Complexity

Brute-Force Approach:

• For each query, examine all pairs in the subarray: O((r-l+1)^2) per query.
• For Q queries, total time: O(Q * N^2), which is infeasible for large N or Q.

• Building prefix sums: O(100 * N), since we do it for each value 1..100.
• For each query, check each of 100 values: O(100) per query.
• Sorting up to 100 values: O(100 log 100) per query (negligible due to small constant).
• Total time: O(100*N + Q*100) = O(N + Q), since 100 is a small constant.
• Space: O(100*N) for prefix sums.

This makes the solution highly efficient and scalable for large inputs.

Summary

The key to solving the Minimum Absolute Difference Queries problem efficiently is recognizing the limited range of values, which allows us to use prefix sums for fast value existence checks in subarrays. By focusing on distinct values and their sorted order, we reduce the problem to a simple minimum difference calculation. This approach avoids brute-force pairwise comparisons, resulting in a highly optimized and elegant solution.

Code Implementation

class Solution:
    def minDifference(self, nums, queries):
        n = len(nums)
        # Build prefix sum for each value from 1 to 100
        prefix = [[0] * (n + 1) for _ in range(101)]
        for i in range(n):
            for v in range(1, 101):
                prefix[v][i + 1] = prefix[v][i]
            prefix[nums[i]][i + 1] += 1

        res = []
        for l, r in queries:
            present = []
            for v in range(1, 101):
                if prefix[v][r + 1] - prefix[v][l] > 0:
                    present.append(v)
            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
      

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<vector<int>> prefix(101, vector<int>(n + 1, 0));
        for (int i = 0; i < n; ++i) {
            for (int v = 1; v <= 100; ++v)
                prefix[v][i + 1] = prefix[v][i];
            prefix[nums[i]][i + 1]++;
        }
        vector<int> res;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            vector<int> present;
            for (int v = 1; v <= 100; ++v) {
                if (prefix[v][r + 1] - prefix[v][l] > 0)
                    present.push_back(v);
            }
            if (present.size() < 2)
                res.push_back(-1);
            else {
                int min_diff = INT_MAX;
                for (int i = 1; i < present.size(); ++i)
                    min_diff = min(min_diff, present[i] - present[i - 1]);
                res.push_back(min_diff);
            }
        }
        return res;
    }
};
      

class Solution {
    public List<Integer> minDifference(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] prefix = new int[101][n + 1];
        for (int i = 0; i < n; ++i) {
            for (int v = 1; v <= 100; ++v)
                prefix[v][i + 1] = prefix[v][i];
            prefix[nums[i]][i + 1]++;
        }
        List<Integer> res = new ArrayList<>();
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            List<Integer> present = new ArrayList<>();
            for (int v = 1; v <= 100; ++v) {
                if (prefix[v][r + 1] - prefix[v][l] > 0)
                    present.add(v);
            }
            if (present.size() < 2)
                res.add(-1);
            else {
                int minDiff = Integer.MAX_VALUE;
                for (int i = 1; i < present.size(); ++i)
                    minDiff = Math.min(minDiff, present.get(i) - present.get(i - 1));
                res.add(minDiff);
            }
        }
        return res;
    }
}
      

var minDifference = function(nums, queries) {
    const n = nums.length;
    const prefix = Array.from({length: 101}, () => new Array(n + 1).fill(0));
    for (let i = 0; i < n; ++i) {
        for (let v = 1; v <= 100; ++v)
            prefix[v][i + 1] = prefix[v][i];
        prefix[nums[i]][i + 1]++;
    }
    const res = [];
    for (const [l, r] of queries) {
        const present = [];
        for (let v = 1; v <= 100; ++v) {
            if (prefix[v][r + 1] - prefix[v][l] > 0)
                present.push(v);
        }
        if (present.length < 2) {
            res.push(-1);
        } else {
            let minDiff = Infinity;
            for (let i = 1; i < present.length; ++i)
                minDiff = Math.min(minDiff, present[i] - present[i - 1]);
            res.push(minDiff);
        }
    }
    return res;
};