https://leetcode.com/problems/frequency-of-the-most-frequent-element/ from Pony.ai

Thinking process:

Since we can only increase the number, if we sort the numbers first, we’ll see something like below after a couple of operations.

The increment we need is very easy to come up. We first make sure what’s the larget number we want. In the above example, it’s 4. Then we need to know how many number we have, it’s 3 in the above example. Finally, we need to know the sum of the numbers, it’s 7 in this case. Then, the increment will be 4*3-7=5, which is less than or equal to k. That’s the answer we want.

However, we don’t want to cover the first number always. For example, if our numbers is [1, 98, 99, 100, 200] and k is 3, then the best answer will be

As you can see, this becomes a sliding window. So, our approach will be for each starting point, we find the ending point of a window where the increment of this window is less or equal to k. Like I mention above, we need to keep tracking the sum of the window.

Here is the code.

 1class Solution {
 2public:
 3    int maxFrequency(vector<int>& nums, int k) {
 4        sort(nums.begin(), nums.end());
 5        int N = nums.size();
 6        long long sum = nums[0];
 7        int ans = 0;
 8        int r = 1;
 9        for (int i=0; i<N; i++) {
10            if (i) {
11                sum -= nums[i-1];
12            }
13            while (r < N and ((long long)nums[r]*(r-i+1)-(sum+nums[r])) <= k) {
14                sum += nums[r];
15                r++;
16            }
17            ans = max(ans, r-i);
18        }
19        return ans;
20    }
21};