1906. Minimum Absolute Difference Queries

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

• For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li…ri] containing the elements of nums between the 0-based indices li and ri (inclusive).

Return an array ans where ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

• x if x >= 0.
• -x if x < 0.

class Solution {
    int psum[101010][101] = {};
public:
    vector<int> minDifference(vector<int>& A, vector<vector<int>>& Q) {
        int n =A.size();
        for(int i = 0; i < n; i++) {
            for(int j = 1; j <= 100; j++) {
                psum[i+1][j] = psum[i][j] + (A[i] == j);
            }
        }
        vector<int> res;
        
        for(auto& q : Q) {
            int mi = INT_MAX, last = 0, l = q[0], r = q[1];
            for(int i = 1; i <= 100; i++) {
                if(psum[r+1][i] - psum[l][i]) {
                    mi = min(mi, last ? i - last : INT_MAX);
                    last = i;
                }
            }
            res.push_back(mi == INT_MAX ? -1 : mi);
        }
        
        
        return res;
    }
};