Frequency of the Most Frequent Element [Medium] — Sorted Window

Problem Statement

Given an array and integer k, the frequency of an element is the count of times it appears. You can increment any element at most k times total. Return the maximum possible frequency.

Input: nums=[1,2,4], k=5 → Output: 3 (make all 4: cost 3+2=5)

Intuition

Sort. The optimal target is always nums[right] (the current right element). Window is valid when nums[right] * window_size - window_sum <= k (cost to raise all elements to nums[right]).

Solutions

C++

int maxFrequency(vector<int>& nums, int k) {
    sort(nums.begin(),nums.end());
    long sum=0; int left=0, ans=1;
    for(int right=0;right<nums.size();right++){
        sum+=nums[right];
        while((long)nums[right]*(right-left+1)-sum>k) sum-=nums[left++];
        ans=max(ans,right-left+1);
    }
    return ans;
}

Java

public int maxFrequency(int[] nums, int k) {
    Arrays.sort(nums);
    long sum=0; int left=0, ans=1;
    for(int right=0;right<nums.length;right++){
        sum+=nums[right];
        while((long)nums[right]*(right-left+1)-sum>k) sum-=nums[left++];
        ans=Math.max(ans,right-left+1);
    }
    return ans;
}

Python

def maxFrequency(nums: list[int], k: int) -> int:
    nums.sort()
    left = ans = 0
    total = 0
    for right, val in enumerate(nums):
        total += val
        while val * (right - left + 1) - total > k:
            total -= nums[left]; left += 1
        ans = max(ans, right - left + 1)
    return ans

Complexity

Time: O(n log n), Space: O(1)