Frequency of the Most Frequent Element

How it works

We can optimize further by observing that we only care about the maximum window size. Once we find a valid window of size w, we never need a smaller window. So instead of shrinking until valid, we can just slide the window forward, maintaining its size when invalid.

If a new element causes the window to become invalid, we remove exactly one element from the left, keeping the window size the same. The window size only grows when we find a valid configuration.

Steps

1. Sort the array.
2. Initialize l = 0 and total = 0.
3. For each right index r:
   • Add nums[r] to total.
   • If (r - l + 1) * nums[r] > total + k:
     • Subtract nums[l] from total and increment l.
4. The final window size is n - l which equals the maximum frequency.
5. Return this value.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Forgetting to Sort the Array

The sliding window and binary search approaches only work on a sorted array. Without sorting, elements that could be incremented to match a target value are scattered throughout the array, making it impossible to find contiguous windows efficiently. Always sort first before applying the window techniques.

Integer Overflow in Cost Calculation

When calculating the cost (window_size) * target - window_sum, the multiplication can overflow if using 32-bit integers. For large arrays with values up to 10^5, the product can exceed 2^31. Use long or long long for the total variable and cast appropriately before multiplication.

Incorrect Window Shrinking Condition

A common mistake is using >= instead of > when checking if the window is invalid. The condition should be nums[r] * (r - l + 1) > total + k (strictly greater), not >=. Using >= would shrink valid windows prematurely, potentially missing the optimal answer.

from typing import List

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        l = 0
        total = 0

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

            if (r - l + 1) * nums[r] > total + k:
                total -= nums[l]
                l += 1

        return len(nums) - l

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long total = 0;
        int l = 0;

        for (int r = 0; r < nums.size(); ++r) {
            total += nums[r];
            if ((r - l + 1) * 1L * nums[r] > total + k) {
                total -= nums[l];
                l++;
            }
        }

        return nums.size() - l;
    }
};