1838. Frequency of the Most Frequent Element

Problem Statement

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

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

Input: nums = [3,9,6], k = 2
Output: 1

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 105

Intuition

Bascially,
We have to find maximum frequency, So if we consider for an array of size 4
So we need to find if we can convert all other to maximum elements in that

So max freq can be N and min 1
1-N we can binary search the window and mid will represent the Sliding window

So if we can acheive the window in k operations

1 4 8 13
Let say window of size 3 
1 4 8 find if can all other can be converted to 8 in k oprations
total operations 8*3 - 1 +4 + 8 find prefix sum for window size

then we can reuse for 4 8 13 shifting window

Video Links

Approach 1:

BS + Prefix sum + Sliding window

C++

class Solution {
public:
    bool possible(vector<int>& nums, int mid, int k){
        long long int window=0;

        for(int i=0; i<mid; i++)
            window += nums[i];

        long long int total = nums[mid-1] * (long long int)mid;

        if(total - window <= k)
            return true;

        int j=0;
        for(int i=mid; i<nums.size(); i++){
            window -= nums[j++];
            window += nums[i];

            long long int total = nums[i] * (long long int)mid;

            if(total - window <= k)
                return true;
        }

        return false;
    }

    int maxFrequency(vector<int>& nums, int k) {
        int low=1, high=nums.size();
        int ans;
        sort(nums.begin(), nums.end());

        while(low<=high){
            int mid = low + (high-low)/2;

            if(possible(nums, mid, k)){
                ans = mid;
                low = mid+1;
            }

            else
                high = mid-1;
        }

        return ans;
    }
};

Approach 2:

Sliding window

Basically in each interval we track if we can convert all the elemets
to last element like this

1 1 1 2 2 4   k=2
  L     R

Here in this interval We try to convert all to Rth element

So (2*4 (Size of interval)) <= Window_sum + K(operations)
Lets check

If that window is changes to 2
2*4 = 8 <= 6+2(opearations = no of values or sum increased)
Allowed here, take that window

C++

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 0, window = 1;
        long long sum = 0;
        int ans = 0;
        sort(nums.begin(), nums.end());
        
        for(int high = 0; high<n; high++){
            sum += nums[high];
            window = high-low+1;

            while((long long)nums[high]*window > sum+k){
                sum -= nums[low++];
                window = high-low+1;
            }
            
            ans = max(window, ans);
        }

        return ans;
    }
};

Approach 3:

C++

Approach 4:

C++