3347. Maximum Frequency of an Element After Performing Operations II

Posted on Edited on In

3347. Maximum Frequency of an Element After Performing Operations II

Description

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 .

Example 1:

1
2
3
Input: nums = [1,4,5], k = 1, numOperations = 2

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

  • Adding 0 to nums[1], after which nums becomes [1, 4, 5].
  • Adding -1 to nums[2], after which nums becomes [1, 4, 4].

Example 2:

1
2
3
Input: nums = [5,11,20,20], k = 5, numOperations = 1

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

  • Adding 0 to nums[1].

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
  • 0 <= numOperations <= nums.length

Hints/Notes

Solution

Language: C++

diff array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        map<int, int> count;
        map<int, int> diff;
        for (int num : nums) {
            count[num]++;
            diff[num];
            diff[num - k] += 1;
            diff[num + k + 1] -= 1;
        }
        int res = 0, cur = 0;
        for (auto it = diff.begin(); it != diff.end(); it++) {
            cur += it->second;
            res = max(res, count[it->first] + min(numOperations, cur - count[it->first]));
        }
        return res;
    }
};

sliding window:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        map<int, int> m;
        for (int num : nums) {
            m[num]++;
        }
        int cur = 0, res = 0;
        auto left = m.begin(), right = m.begin();
        for (auto i = m.begin(); i != m.end(); i++) {
            while (left->first + k < i->first) {
                cur -= left->second;
                left++;
            }
            while (right != m.end() && right->first <= i->first + k) {
                cur += right->second;
                right++;
            }
            res = max(res, i->second + min(cur - i->second, numOperations));

        }
        if (res >= numOperations) {
            return res;
        }

        // the sliding window case
        cur = 0, left = m.begin(), right = m.begin();
        while (right != m.end()) {
            cur += right->second;
            while (left->first < right->first - 2 * k) {
                cur -= left->second;
                left++;
            }
            res = max(res, cur);
            right++;
        }
        return min(res, numOperations);
    }
};