Frequency of the Most Frequent Element

LeetCode 1838 Frequency of the Most Frequent Element asks you to find the maximum possible frequency of any element after performing at most k increment operations. Each operation lets you pick one element and increase it by 1. You want to make as many elements equal as possible.

For example, given nums = [1, 2, 4] and k = 5, you can increment 1 three times and 2 twice, spending all 5 operations to make every element 4. The answer is 3.

The key insight is that sorting unlocks a sliding window approach. After sorting, the elements you want to equalize will always be a contiguous group, and you always want to raise them all up to match the largest one in the window.

Why sorting makes this work

Without sorting, you would need to consider every possible subset of elements to equalize, which is exponential. But think about what the increment operations actually do: they can only increase values, never decrease them. So if you want to make a group of elements equal, you are raising the smaller ones up to match the largest.

After sorting, the cheapest group of elements to equalize is always a contiguous subarray. Why? Because the elements closest in value to your target require the fewest operations. Sorting puts similar values next to each other, so any optimal group forms a contiguous window.

Once you see this, the problem becomes: find the longest contiguous window in the sorted array where the cost to make every element equal to the rightmost (largest) element is at most k.

The cost formula

For a window from index left to right in the sorted array, the cost to make all elements equal to nums[right] is:

cost = nums[right] * window_size - sum(nums[left..right])

This is because you need nums[right] * window_size total value (every element becomes nums[right]), and you already have sum(nums[left..right]). The difference is the number of increments you need.

You can maintain this cost incrementally as you slide the window. When you expand right, add the new difference. When you shrink left, subtract the old difference. This keeps each step O(1).

The sliding window approach

Here is the plan:

1. Sort the array.
2. Use two pointers left and right to define a window.
3. Track the running sum of elements in the window.
4. For each right, check if the cost to equalize the window exceeds k. If it does, shrink from the left until the window is valid again.
5. Track the maximum window size seen.

def maxFrequency(nums, k):
    nums.sort()
    left = 0
    total = 0
    best = 0

    for right in range(len(nums)):
        total += nums[right]

        while nums[right] * (right - left + 1) - total > k:
            total -= nums[left]
            left += 1

        best = max(best, right - left + 1)

    return best

The while loop shrinks the window whenever nums[right] * window_size - total > k. Once the window is valid, right - left + 1 gives the current frequency. We track the maximum across all positions of right.

Why the inner while loop is still O(n) total

The while loop inside the for loop might look like it could cause O(n^2) behavior. But left only moves forward and never resets. Across the entire run of the algorithm, left moves at most n times total. So the total work from the inner loop across all iterations of the outer loop is O(n). Combined with the O(n log n) sort, the overall time complexity is O(n log n).

Complexity analysis

The sorting step dominates at O(n log n). The sliding window pass is O(n). Space is O(1) beyond the input (assuming in-place sort), or O(n) if your language creates a copy during sorting.

The building blocks

This problem combines two fundamental patterns that appear across many LeetCode problems:

1. Sorting to create structure

Sorting transforms a chaotic problem into one with exploitable order. Once sorted, "closest values" are adjacent, and the optimal group to equalize is always contiguous. This same idea appears in problems like 3Sum, Merge Intervals, and Meeting Rooms. Whenever you notice that the answer involves "nearby" values, sorting is worth considering.

2. Sliding window with a cost budget

The window tracks a contiguous subarray and maintains a running cost. When the cost exceeds the budget k, you shrink from the left. This is the same expand-then-shrink pattern from Minimum Window Substring and Minimum Size Subarray Sum. The only difference is what "cost" means: here it is the total increments needed, elsewhere it might be character frequencies or subarray sums.

These two blocks snap together cleanly: sorting creates the structure, and the sliding window exploits it.

Edge cases

Before submitting, make sure your solution handles:

• All elements already equal: nums = [3, 3, 3], k = 0. The answer is 3 with zero operations needed.
• k is zero: No operations allowed. The answer is the highest existing frequency in the array.
• Single element: nums = [5]. The answer is always 1.
• k is very large: Enough budget to make every element equal to the max. The answer is n.
• Large values with small k: nums = [1, 1000000], k = 1. You cannot bridge the gap. The answer is 1.

Binary search alternative

There is an alternative approach using binary search on the answer. You binary search for the maximum frequency f, and for each candidate f, check whether any window of size f in the sorted array can be equalized within k operations. The check uses a sliding window of fixed size f, making it O(n) per check and O(n log n) overall (the same as the pure sliding window approach). Both solutions have the same complexity, but the pure sliding window version is simpler to implement and reason about.

From understanding to recall

You understand the solution now: sort, slide, track cost, shrink when over budget. But understanding is not the same as being able to reproduce it under pressure. In a week, will you remember the cost formula? Will you remember that sorting is the critical first step? Will you mix up whether to shrink when cost exceeds k or when it is below k?

Spaced repetition solves this by having you write the solution from scratch at increasing intervals. The first review might be tomorrow. Then three days later. Then a week. Each time you reconstruct the code, the pattern gets more automatic. By the time you see a similar problem in an interview, sorting-plus-sliding-window is reflex, not recall.

Related posts

• Longest Substring Without Repeating Characters - The classic sliding window problem with a different validity condition
• Minimum Window Substring - A harder shrinking-window variant that uses frequency counting
• Sliding Window Maximum - Another sliding window problem that combines sorting ideas with window mechanics