AlgoInsight

DSA problem

Frequency of the Most Frequent Element

MediumSliding Window - Dynamic SizePattern: Variable-Size Sliding Windowtop600AmazonGoogleMicrosoftMeta

The frequency of an element is the number of times it occurs in an array. You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Since increments only ever raise values, the optimal target to converge on is always one of the existing array values, and it is most efficient to raise a group of smaller elements up to a larger one. If you sort the array, any group of elements you wish to make equal becomes a contiguous segment, and the cheapest target for that segment is its largest (rightmost) element.

After sorting, slide a variable-size window across the array. For a window ending at right, the cost to lift every element up to nums[right] is nums[right] * windowLength - windowSum. While that cost exceeds k, shrink the window from the left, subtracting elements from the running sum. The widest window whose cost stays within k gives the maximum achievable frequency.

Examples

Example 1
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4]. This uses 5 operations and produces three equal elements, the largest possible frequency.
Example 2
Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions, such as incrementing the first element three times to get nums = [4,4,8,13], or incrementing the third element five times. Each produces a frequency of 2.
Example 3
Input: nums = [3,9,6], k = 2
Output: 1
Explanation: No two elements can be made equal with at most 2 operations, so the maximum frequency stays at 1.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowsortingarraygreedyprefix-sum

Browse all DSA problems