Frequency of the Most Frequent Element — Problem & Solution
Frequency of the Most Frequent Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Frequency of the Most Frequent Element is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Salesforce interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search, Sliding Window
- Asked at: Amazon, Google, Salesforce
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one operation you may increment any element of nums by 1. You may perform at most k operations in total.
Return the maximum possible frequency of any single value afterwards.
Example 1
Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Raise 1 to 4 (3 operations) and 2 to 4 (2 more) — every element becomes 4.
Example 2
Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: Raising 4 to 8 costs 4.
Example 3
Input: nums = [3,9,6], k = 2
Output: 1
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 1000001 <= k <= 100000000
Hints for Frequency of the Most Frequent Element
Hint 1
Only increments are allowed, so the final common value must be one of the existing elements — the largest in the group.
Hint 2
Sort, then ask: for a window ending at
r, what does it cost to raise everything in it tonums[r]?Hint 3
That cost is
nums[r] · windowSize − windowSum, which grows as the window widens.
How to solve Frequency of the Most Frequent Element
Sorting makes the cheapest group of equal values contiguous, because raising an element to a target costs the gap and you would never skip a nearer element for a further one. The cost of a window is then a closed form, and it is monotone in the window's width.
Approach
- Sort
nums. - Slide a window; on adding
a[r], the cost to level the window toa[r]isa[r] · (r - l + 1) - windowSum. - While that exceeds
k, dropa[l]and advancel. - Track the widest valid window.
Why it works
With increments only, the target must be the window's maximum, which after sorting is a[r]. Widening the window on the left adds a smaller element, so the levelling cost only ever increases — the predicate is monotone and a single left pointer suffices. Each index enters and leaves once.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
a[r] · windowSizereaches10^5 · 10^5 = 10^10— the arithmetic needs 64-bit even though the answer is small.- Targeting a value not present in the array is never better, since lowering the target can only reduce the cost.
- The answer is at least 1, so seed the best accordingly.
Reference solution
Python
from typing import List
def maxFrequency(nums: List[int], k: int) -> int:
a = sorted(nums)
l = 0
total = 0
best = 1
for r in range(len(a)):
total += a[r]
while a[r] * (r - l + 1) - total > k:
total -= a[l]
l += 1
best = max(best, r - l + 1)
return bestJava
public static int maxFrequency(int[] nums, int k) {
int[] a = nums.clone();
Arrays.sort(a);
int l = 0, best = 1;
long sum = 0;
for (int r = 0; r < a.length; r++) {
sum += a[r];
while ((long) a[r] * (r - l + 1) - sum > k) {
sum -= a[l];
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}C++
int maxFrequency(vector<int>& nums, int k) {
vector<int> a = nums;
sort(a.begin(), a.end());
int l = 0, best = 1;
long long sum = 0;
for (int r = 0; r < (int) a.size(); r++) {
sum += a[r];
while ((long long) a[r] * (r - l + 1) - sum > k) {
sum -= a[l];
l++;
}
best = max(best, r - l + 1);
}
return best;
}JavaScript
var maxFrequency = function(nums, k) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var l = 0, sum = 0, best = 1;
for (var r = 0; r < a.length; r++) {
sum += a[r];
while (a[r] * (r - l + 1) - sum > k) { sum -= a[l]; l++; }
if (r - l + 1 > best) best = r - l + 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms