Frequency of the Most Frequent Element

1. Define the problem

Frequency of the Most Frequent Element

You are given an integer array nums and an integer k. In one operation, you can choose an index and increment nums at that index by 1, using at most k operations total. Return the maximum possible frequency of any single element after performing the operations . Sort the array, then grow a window where the cost to raise every element up to the current right value stays within budget, shrinking from the left whenever it does not.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums_i ≤ 10⁵
1 ≤ k ≤ 10⁵

Example

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

Output3

Explanation Add 3 to the 1 and 2 to the 2, using 5 operations, to make [4, 4, 4].

2. Know the words first

In plain terms

Frequency: The number of times a value appears in a collection — the frequency of 4 in [1, 4, 4, 4] is 3.

3. Visualize the solution

Sorted window kept within the raise budget

Statusvalid

Window [1]; cost to raise to 1 is 0 <= 5; best = 1.

What happens in this step

sorted = [1, 2, 4]
right=0: windowSum = 1
  cost = sorted[right] * length - windowSum = 1 * 1 - 1 = 0
  0 <= k=5 → within budget, no shrink
  best = max(1, 1) = 1

Step 1 of 3

Steps to visualize

Sort the array so every window is a contiguous run of nearby values.
Grow right and add its value into a running window sum.
The cost to raise the window to the right value is (right value * window length) - window sum.
While that cost exceeds k, shrink from the left and adjust the sum.
Track the longest window length seen — that is the best achievable frequency.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sorted window kept within the raise budget

Statusvalid

Window [1]; cost to raise to 1 is 0 <= 5; best = 1.

What happens in this step

sorted = [1, 2, 4]
right=0: windowSum = 1
  cost = sorted[right] * length - windowSum = 1 * 1 - 1 = 0
  0 <= k=5 → within budget, no shrink
  best = max(1, 1) = 1

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function maxFrequency(nums, k) {
  const sorted = [...nums].sort((a, b) => a - b);
  let left = 0;
  let windowSum = 0;
  let best = 1;

  for (let right = 0; right < sorted.length; right++) {
    windowSum += sorted[right];

    while (sorted[right] * (right - left + 1) - windowSum > k) {
      windowSum -= sorted[left];
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 4], k = 5`	`3`	Docstring example
`nums = [1, 2, 3], k = 0`	`1`	k = 0 with all distinct elements
`nums = [5], k = 3`	`1`	Single element
`nums = [1, 4, 8, 13], k = 1000`	`4`	k large enough to raise the whole array
`nums = [1, 1, 2, 4], k = 0`	`2`	k = 0 returns the existing max frequency
`nums = [1, 4, 8, 13], k = 5`	`2`	Budget only enough to merge one adjacent pair
`nums = [3, 9], k = 2`	`1`	Budget too small to merge any pair

Frequency of the Most Frequent Element