Frequency of the Most Frequent Element
Medium · Sliding Window · Array · Binary Search · Greedy · Sliding Window · Sorting · Prefix Sum
Problem
The frequency of a value is how many times it occurs in an array. You are given an integer array nums and a budget k. In one operation you may pick any index and increase nums[i] by 1.
Using at most k operations, return the highest frequency any single value can reach.
Examples
Input: nums = [1,2,4], k = 5 Output: 3
Raising 1 by 3 and 2 by 2 uses all 5 operations and makes every element 4.
Input: nums = [3,9,6], k = 2 Output: 1
Every pair of values is at least 3 apart, which is more than the budget.
Input: nums = [1,4,8,13], k = 5 Output: 2
Raising 1 to 4 costs 3 and gives frequency 2; 4 to 8 costs 4 and also gives 2. No three values fit in 5 operations.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^5
- 1 <= k <= 10^5
Approaches
- Sort, then grow left from each target — time O(n²), space O(n) for the sorted copy
Follow-up
What if you may also decrease values? Then the best target for a window is its median, not its largest value, and the cost of a window is the distance of every value to the median, which prefix sums give in O(1). The window is still monotone, so the same two-pointer walk works.
Related problems
Start free on Cariara · Coding problems · System design studio
