Frequency of the Most Frequent Element

medium sliding window sorting greedy

Problem

Each operation adds 1 to any element. Given k operations, return the largest frequency some value can reach.

Inputnums = [1,2,4], k = 5

Output3

Sort → [1,2,4]; raise 1→4, 2→4 costs 3+2=5; all three equal.

nums

def max_frequency(nums, k):
    nums.sort()
    left = 0
    cur = 0
    best = 0
    for right in range(len(nums)):
        cur += nums[right]
        while nums[right] * (right - left + 1) - cur > k:
            cur -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

function maxFrequency(nums, k) {
  nums.sort((a, b) => a - b);
  let left = 0, cur = 0, best = 0;
  for (let right = 0; right < nums.length; right++) {
    cur += nums[right];
    while (nums[right] * (right - left + 1) - cur > k) {
      cur -= nums[left]; left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

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

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

Explanation

We can add 1 to any element, up to k times total, and want the largest group of equal values we can create. The key insight is that it is always cheapest to raise smaller numbers up to a larger target, so we first sort the array.

After sorting, we slide a window and treat its rightmost (largest) value as the target everyone in the window should reach. The cost to lift the whole window to nums[right] is nums[right] * windowLength - windowSum: the total if every slot already equaled the target, minus what they currently sum to.

We keep a running cur sum of the window. While the cost exceeds k, we shrink from the left. Every valid window length is a candidate, and we track the largest in best.

Example: nums = [1,2,4], k = 5. With target 4 over the whole window, the cost is 4*3 - (1+2+4) = 12 - 7 = 5, which fits the budget, so all three can be made equal and the answer is 3.

Sorting dominates at n log n; the sliding window itself is linear because each index enters and leaves once.

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