Description

Submission

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();

        vector<vector<int>> presum(101, vector<int>(n, 0));

        for(int i = 0; i < 101; ++i) {
            for(int j = 0; j < nums.size(); ++j) {
                presum[i][j] = (j == 0) ? (nums[j] == i) : presum[i][j-1] + (nums[j] == i);
            }
        }

        vector<int> rets;
        for(auto& query: queries) {
            int a = query[0];
            int b = query[1];
            int gap = INT_MAX;
            vector<int> tmp;

            for(int i = 0; i < 101; ++i) {
                if((a == 0) ? presum[i][b] : (presum[i][b] - presum[i][a-1])) tmp.push_back(i);
                int t = tmp.size();
                if(t >= 2) {
                    gap = min(gap, tmp[t-1] - tmp[t-2]);
                    if(gap == 1) {
                        break;
                    }
                }
            }
            
            if(gap == INT_MAX) {
                rets.push_back(-1);
            } else {
                rets.push_back(gap);
            }
        }
        
        return rets;
    }
};


// X X X X X [X X X X] X X

// traverse nums[i]