3346. Maximum Frequency of an Element After Performing Operations I

Posted on Edited on In

3346. Maximum Frequency of an Element After Performing Operations I

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]. nums becomes [1, 4, 5].
  • Adding -1 to nums[2]. 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^5
  • 0 <= k <= 10^5
  • 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;
    }
};