3347. Maximum Frequency of an Element After Performing Operations II

You are given an integer array nums and two integers k and numOperations.

You must perform an operation numOperations times on nums, where in each operation you:

• Select an index i that was not selected in any previous operations.
• Add an integer in the range [-k, k] to nums[i].

Return the maximum possible frequency of any element in nums after performing the operations.

The frequency of an element x is the number of times it occurs in the array.

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        unordered_map<int,int> freq;
        for(auto& n : nums) {
            freq[n]++;
            freq[n-k] += 0;
            freq[n+k] += 0;
        }
        vector<pair<int,int>> S;
        for(auto& [k,v] : freq) S.push_back({k,v});
        sort(begin(S), end(S));
        int res = 0, n = S.size();
        for(int i = 0, l = 0, r = 0, cnt = 0; i < n; i++) {
            while(S[l].first < S[i].first - k) {
                cnt -= S[l++].second;
            }
            while(r < n and S[r].first <= S[i].first + k) {
                cnt += S[r++].second;
            }
            res = max(res, S[i].second + min(cnt - S[i].second, numOperations));
        }
        return res;
    }
};