Frequency of the Most Frequent Element
Description
You are given an integer array nums and an integer k. The frequency of an element is the number of times it appears in the array.
In one operation, you can pick any element from the array and increment its value by 1. You may perform at most k operations in total.
Return the maximum possible frequency of any element after performing at most k operations.
The key constraint is that you can only increment elements — never decrement. So if you want to make several elements equal, you must raise smaller values up to match a larger target value. Your goal is to choose the smartest target value and the best group of elements to boost, spending the fewest operations to create the highest frequency.
Examples
Example 1
Input: nums = [1, 2, 4], k = 5
Output: 3
Explanation: We can increment nums[0] = 1 three times (1 → 4) using 3 operations, and increment nums[1] = 2 two times (2 → 4) using 2 operations. Total operations = 3 + 2 = 5, which is within our budget. The array becomes [4, 4, 4], so element 4 has a frequency of 3. No better frequency is possible.
Example 2
Input: nums = [1, 4, 8, 13], k = 5
Output: 2
Explanation: There are multiple ways to achieve frequency 2:
- Increment 1 three times to get [4, 4, 8, 13] → frequency of 4 is 2 (cost 3)
- Increment 4 four times to get [1, 8, 8, 13] → frequency of 8 is 2 (cost 4)
- Increment 8 five times to get [1, 4, 13, 13] → frequency of 13 is 2 (cost 5)
All use ≤ 5 operations. But achieving frequency 3 would require too many operations for any target value, so 2 is the maximum.
Example 3
Input: nums = [3, 9, 6], k = 2
Output: 1
Explanation: The gaps between elements are too large relative to k = 2. The cheapest pairing would be making 6 → 9 (cost 3), but that exceeds our budget. No two elements can be made equal with only 2 operations, so the best we can do is frequency 1 — every element appears exactly once.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^5
- 1 ≤ k ≤ 10^5
Editorial
Brute Force
Intuition
The most straightforward way to think about this problem: try every possible target value, and for each target, figure out how many elements we can raise to match it within our budget of k operations.
Since we can only increment elements, we should only consider raising smaller elements up to the target. For a given target value, the cheapest elements to convert are those closest to the target (they need the fewest increments). So we should sort the array first, then for each potential target, greedily pick the closest smaller elements.
After sorting, for each element nums[i] as the target, we look backward at elements nums[i-1], nums[i-2], ... and try to bring each one up to nums[i]. We keep going as long as our total operation cost stays within k. The number of elements we can bring up (including the target itself) is the frequency for that target.
We repeat this for every element as the target and take the maximum frequency found.
Step-by-Step Explanation
Let's trace through with nums = [1, 2, 4], k = 5. After sorting: [1, 2, 4].
Step 1: Try target = nums[0] = 1. Only one element equals or is below 1. Frequency = 1.
Step 2: Try target = nums[1] = 2. Cost to raise nums[0]=1 to 2: 2 - 1 = 1. Total cost = 1 ≤ 5. Both elements match. Frequency = 2.
Step 3: Try target = nums[2] = 4. Start expanding backward from index 2.
- Cost to raise nums[1]=2 to 4: 4 - 2 = 2. Running total = 2 ≤ 5. Count = 2.
- Cost to raise nums[0]=1 to 4: 4 - 1 = 3. Running total = 2 + 3 = 5 ≤ 5. Count = 3.
- All elements included. Frequency = 3.
Step 4: Maximum across all targets: max(1, 2, 3) = 3.
Result: 3
Brute Force — Try Each Element as Target — For each element in the sorted array, we expand backward to see how many elements can be raised to match it within k operations.
Algorithm
- Sort the array in non-decreasing order
- Initialize
best_freq = 1 - For each index
ifrom 0 to n-1 (this element is the target):
a. Setcost = 0,count = 1(the target itself)
b. For each indexjfromi-1down to 0:- Add
nums[i] - nums[j]tocost - If
cost > k, break - Otherwise increment
count
c. Updatebest_freq = max(best_freq, count)
- Add
- Return
best_freq
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1;
for (int i = 0; i < n; i++) {
long long cost = 0;
int count = 1;
for (int j = i - 1; j >= 0; j--) {
cost += nums[i] - nums[j];
if (cost > k) break;
count++;
}
best = max(best, count);
}
return best;
}
};class Solution:
def maxFrequency(self, nums: list[int], k: int) -> int:
nums.sort()
n = len(nums)
best = 1
for i in range(n):
cost = 0
count = 1
for j in range(i - 1, -1, -1):
cost += nums[i] - nums[j]
if cost > k:
break
count += 1
best = max(best, count)
return bestimport java.util.Arrays;
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int best = 1;
for (int i = 0; i < n; i++) {
long cost = 0;
int count = 1;
for (int j = i - 1; j >= 0; j--) {
cost += nums[i] - nums[j];
if (cost > k) break;
count++;
}
best = Math.max(best, count);
}
return best;
}
}Complexity Analysis
Time Complexity: O(n²)
Sorting takes O(n log n). Then for each of the n elements as target, we may scan up to n elements backward in the worst case. This gives O(n) × O(n) = O(n²) for the nested loops. Overall: O(n² + n log n) = O(n²).
Space Complexity: O(1) (excluding sorting space)
We only use a few variables (cost, count, best). The sort may use O(log n) stack space depending on implementation, but no additional data structures are needed.
Why This Approach Is Not Efficient
The brute force runs in O(n²) time. With n up to 10^5, that's up to 10^10 operations — far too slow for typical time limits of 1-2 seconds.
The core inefficiency: for each target, we scan backward element-by-element to accumulate cost. When we move to the next target (one position to the right), we throw away all the work we did and start fresh. But the windows for adjacent targets overlap heavily!
Consider targets at index 5 and index 6. The window for target 5 might include indices [2, 3, 4, 5]. The window for target 6 includes many of the same elements — maybe [3, 4, 5, 6]. We recompute the cost from scratch instead of reusing the previous window's information.
This observation suggests a sliding window approach: as we move the target rightward, we can expand the window right edge and shrink the left edge, maintaining a running total of cost. This avoids redundant computation and brings the time down from O(n²) to O(n).
Better Approach - Sorting + Prefix Sum + Binary Search
Intuition
Before jumping to the sliding window, there's an elegant intermediate approach using binary search.
The key insight: after sorting, for a fixed target nums[right], the cost to raise all elements in a window [left, right] to nums[right] is:
cost = nums[right] × window_size - sum(nums[left..right])
This is because every element in the window must become nums[right]. The total value needed is nums[right] × window_size, and the total value already present is the sum of the window. The difference is the number of operations required.
We can compute sum(nums[left..right]) in O(1) time using a prefix sum array.
Now, for each right (the target element), we want the leftmost left such that the cost stays within k. Since the cost increases as the window grows (more elements to raise), we can binary search for the optimal left position.
For each right index, we binary search over possible left indices, checking if the cost for the window [left, right] is ≤ k. The frequency for that target is right - left + 1.
Step-by-Step Explanation
Let's trace with nums = [1, 4, 8, 13], k = 5. Already sorted.
Prefix sums: prefix = [0, 1, 5, 13, 26]
Step 1: Target = nums[0] = 1, right = 0. Binary search for smallest left in [0, 0]. Only window [0, 0], cost = 1×1 - 1 = 0 ≤ 5. Frequency = 1.
Step 2: Target = nums[1] = 4, right = 1. Binary search for smallest left in [0, 1].
- Try left = 0: window = [1, 4]. Cost = 4×2 - (prefix[2] - prefix[0]) = 8 - 5 = 3 ≤ 5. Left can be 0. Frequency = 2.
Step 3: Target = nums[2] = 8, right = 2. Binary search for smallest left in [0, 2].
- Try left = 0: window = [1, 4, 8]. Cost = 8×3 - (prefix[3] - prefix[0]) = 24 - 13 = 11 > 5. Too expensive.
- Try left = 1: window = [4, 8]. Cost = 8×2 - (prefix[3] - prefix[1]) = 16 - 12 = 4 ≤ 5. Frequency = 2.
Step 4: Target = nums[3] = 13, right = 3. Binary search for smallest left in [0, 3].
- Try left = 1: window = [4, 8, 13]. Cost = 13×3 - (prefix[4] - prefix[1]) = 39 - 25 = 14 > 5.
- Try left = 2: window = [8, 13]. Cost = 13×2 - (prefix[4] - prefix[2]) = 26 - 21 = 5 ≤ 5. Frequency = 2.
Step 5: Maximum across all: max(1, 2, 2, 2) = 2.
Result: 2
Prefix Sum + Binary Search — Finding Optimal Window per Target — For each target (right end), binary search finds the widest window whose cost stays within k, using prefix sums for O(1) window sum queries.
Algorithm
- Sort the array
- Build prefix sum array:
prefix[i] = prefix[i-1] + nums[i-1] - For each index
rightfrom 0 to n-1 (target = nums[right]):
a. Binary search for the smallestleftsuch that:
nums[right] × (right - left + 1) - (prefix[right+1] - prefix[left]) ≤ k
b. The frequency for this target isright - left + 1
c. Updatebest_freq = max(best_freq, right - left + 1) - Return
best_freq
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
// Build prefix sum
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int best = 1;
for (int right = 0; right < n; right++) {
// Binary search for smallest left
int lo = 0, hi = right;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long long windowSize = right - mid + 1;
long long windowSum = prefix[right + 1] - prefix[mid];
long long cost = (long long)nums[right] * windowSize - windowSum;
if (cost <= k) {
hi = mid; // try wider window
} else {
lo = mid + 1; // window too expensive
}
}
best = max(best, right - lo + 1);
}
return best;
}
};class Solution:
def maxFrequency(self, nums: list[int], k: int) -> int:
nums.sort()
n = len(nums)
# Build prefix sum
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 1
for right in range(n):
# Binary search for smallest left
lo, hi = 0, right
while lo < hi:
mid = lo + (hi - lo) // 2
window_size = right - mid + 1
window_sum = prefix[right + 1] - prefix[mid]
cost = nums[right] * window_size - window_sum
if cost <= k:
hi = mid # try wider window
else:
lo = mid + 1 # window too expensive
best = max(best, right - lo + 1)
return bestimport java.util.Arrays;
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
// Build prefix sum
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int best = 1;
for (int right = 0; right < n; right++) {
// Binary search for smallest left
int lo = 0, hi = right;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long windowSize = right - mid + 1;
long windowSum = prefix[right + 1] - prefix[mid];
long cost = (long) nums[right] * windowSize - windowSum;
if (cost <= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
best = Math.max(best, right - lo + 1);
}
return best;
}
}Complexity Analysis
Time Complexity: O(n log n)
Sorting takes O(n log n). Building the prefix sum takes O(n). For each of n elements, we perform a binary search over at most n positions, taking O(log n) per search. Total: O(n log n) + O(n) + O(n log n) = O(n log n).
Space Complexity: O(n)
The prefix sum array requires O(n) additional space. This is a significant improvement over the brute force's O(n²) time, but we can do even better.
Why This Approach Is Not Efficient
The binary search approach runs in O(n log n), which is efficient enough to pass. However, it's not truly optimal in the strictest sense because the binary search does redundant work.
Notice a crucial monotonicity property: as the right pointer moves from index i to i+1, the optimal left pointer either stays in place or moves right — it never moves left. This is because nums[i+1] ≥ nums[i] (sorted array), so the cost per element in the window only increases. The window can only shrink or stay the same as the target grows.
This monotonicity means the left and right pointers both only move forward through the array, which is exactly the pattern for a sliding window (two-pointer) approach. Instead of binary searching for left at each right, we can simply advance left whenever the cost exceeds k. Each pointer moves at most n times, giving O(n) total for the window phase — an improvement over the O(n log n) binary search phase.
Optimal Approach - Sorting + Sliding Window
Intuition
The sliding window approach is built on three insights:
Insight 1: Sort first. Since we can only increment, we want to raise smaller elements to a larger target. After sorting, the closest (cheapest-to-raise) elements are adjacent, so we only need to consider contiguous windows.
Insight 2: Target is always the rightmost element. Within a sorted window [left, right], the target value is nums[right] — the largest element. Every other element in the window must be raised to this value.
Insight 3: The window is monotonic. As we slide right forward (increasing the target value), the window can only shrink or grow — the left boundary never moves backward. This is because a larger target means higher cost per element, so we may need to shrink the window from the left to stay within budget.
We maintain a running sum of the window. The cost to make all elements equal to nums[right] is:
cost = nums[right] × window_size - window_sum
If this cost exceeds k, we shrink from the left (subtract nums[left] from the running sum, advance left). Otherwise, we record the window size as a candidate answer and expand right.
This way, both pointers sweep the array once — total O(n) for the window phase.
Step-by-Step Explanation
Let's trace with nums = [1, 2, 4], k = 5. Already sorted.
Step 1: Initialize left = 0, window_sum = 0, best = 0.
Step 2: right = 0. Add nums[0] = 1 to window_sum → window_sum = 1. Window = [1]. Cost = 1×1 - 1 = 0 ≤ 5. Window size = 1. best = 1.
Step 3: right = 1. Add nums[1] = 2 to window_sum → window_sum = 3. Window = [1, 2]. Cost = 2×2 - 3 = 1 ≤ 5. Window size = 2. best = 2.
Step 4: right = 2. Add nums[2] = 4 to window_sum → window_sum = 7. Window = [1, 2, 4]. Cost = 4×3 - 7 = 5 ≤ 5. Exactly at budget! Window size = 3. best = 3.
Step 5: All elements processed. Return best = 3.
Now let's also trace the second example: nums = [1, 4, 8, 13], k = 5.
Step 1: left = 0, window_sum = 0, best = 0.
Step 2: right = 0. window_sum = 1. Window = [1]. Cost = 0 ≤ 5. best = 1.
Step 3: right = 1. window_sum = 5. Window = [1, 4]. Cost = 4×2 - 5 = 3 ≤ 5. best = 2.
Step 4: right = 2. window_sum = 13. Window = [1, 4, 8]. Cost = 8×3 - 13 = 11 > 5. Shrink! Remove nums[0]=1, left → 1, window_sum = 12. Window = [4, 8]. Cost = 8×2 - 12 = 4 ≤ 5. Window size = 2. best stays 2.
Step 5: right = 3. window_sum = 25. Window = [4, 8, 13]. Cost = 13×3 - 25 = 14 > 5. Shrink! Remove nums[1]=4, left → 2, window_sum = 21. Window = [8, 13]. Cost = 13×2 - 21 = 5 ≤ 5. Window size = 2. best stays 2.
Step 6: Return best = 2.
Sliding Window — Expand Right, Shrink Left — Watch the sliding window expand by moving right to include new elements, and shrink by advancing left when the cost exceeds k. Both pointers only move forward.
Algorithm
- Sort the array in non-decreasing order
- Initialize
left = 0,window_sum = 0,best = 0 - For each
rightfrom 0 to n-1:
a. Addnums[right]towindow_sum
b. Whilenums[right] × (right - left + 1) - window_sum > k:- Subtract
nums[left]fromwindow_sum - Increment
left
c. Updatebest = max(best, right - left + 1)
- Subtract
- Return
best
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int left = 0, best = 0;
long long windowSum = 0;
for (int right = 0; right < n; right++) {
windowSum += nums[right];
// Shrink window while cost exceeds k
while ((long long)nums[right] * (right - left + 1) - windowSum > k) {
windowSum -= nums[left];
left++;
}
best = max(best, right - left + 1);
}
return best;
}
};class Solution:
def maxFrequency(self, nums: list[int], k: int) -> int:
nums.sort()
left = 0
window_sum = 0
best = 0
for right in range(len(nums)):
window_sum += nums[right]
# Shrink window while cost exceeds k
while nums[right] * (right - left + 1) - window_sum > k:
window_sum -= nums[left]
left += 1
best = max(best, right - left + 1)
return bestimport java.util.Arrays;
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, best = 0;
long windowSum = 0;
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right];
// Shrink window while cost exceeds k
while ((long) nums[right] * (right - left + 1) - windowSum > k) {
windowSum -= nums[left];
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
}Complexity Analysis
Time Complexity: O(n log n)
Sorting takes O(n log n). The sliding window phase is O(n) because the left pointer moves at most n times across the entire execution and the right pointer moves exactly n times. Each element is added to the window once (when right passes it) and removed at most once (when left passes it). The total pointer movements are bounded by 2n = O(n). The bottleneck is the sort.
Space Complexity: O(1) (excluding sorting space)
We only use a few variables: left, windowSum, and best. Unlike the prefix sum approach, we don't need any auxiliary array. The sort may use O(log n) space internally.
This is optimal: we must sort to identify adjacent cheapest elements, and sorting is Ω(n log n). The sliding window phase is already O(n). No further improvement is possible without a fundamentally different problem model.