Apply Operations to Maximize Frequency Score — Solution
Apply Operations to Maximize Frequency Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Apply Operations to Maximize Frequency Score is a hard coding problem on arrays, sorting and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- 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
You are given an integer array nums and an integer k. You may perform the following operation at most k times in total: choose any index i and increase or decrease nums[i] by 1.
The score of the final array is the frequency of its most frequent element.
Return the maximum score you can achieve.
CodeKairo note: the original allows k up to 10^14; here k is a 32-bit integer (k <= 10^9). The cost of a window can still exceed 32 bits — compute it in 64-bit.
Example 1
Input: nums = [7,1,3,9], k = 6
Output: 3
Explanation: Turn 1 into 3 (2 operations) and 7 into 3 (4 operations): three 3s for exactly 6 operations.
Example 2
Input: nums = [5,5,2,5], k = 0
Output: 3
Explanation: No operations are allowed; 5 already appears three times.
Example 3
Input: nums = [10,20], k = 9
Output: 1
Explanation: Making the two equal needs 10 operations.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= k <= 10^9
Hints for Apply Operations to Maximize Frequency Score
Hint 1
Sort the array. The elements you make equal can be taken as a contiguous block of the sorted array — swapping in a closer element never costs more.
Hint 2
For a fixed block, the cheapest common value is its median, and the cost is the sum of distances to the median. Prefix sums give it in O(1).
Hint 3
The cost of a block grows when you extend it and shrinks when you drop its leftmost element, so slide a window: extend right, and move left forward while the cost exceeds
k.
How to solve Apply Operations to Maximize Frequency Score
After sorting, the best set of elements to equalise is a contiguous window, and the cheapest target for a window is its median. The window's cost is monotone, so two pointers find the longest affordable window.
Approach
- Sort
numsand build prefix sumsP(64-bit). - Define
cost(l, r)withm = (l + r) / 2:a[m]·(m - l) - (P[m] - P[l]) + (P[r+1] - P[m+1]) - a[m]·(r - m)— the total distance from every element of the window to its median. - Keep
left = 0. For eachright, advanceleftwhilecost(left, right) > k. - Track the maximum
right - left + 1.
Why it works
Fix the final common value t. Making c elements equal to t is cheapest with the c elements closest to t, which form a contiguous block of the sorted array; and for a fixed block, the sum of absolute distances is minimised at a median. So the answer is the longest window whose median-cost is at most k. That cost never decreases when the window gains an element and never increases when it loses its leftmost one, which justifies moving left only forward.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Costs reach about 5·10^13 — prefix sums and the cost must be 64-bit.
- Targeting the mean instead of the median can cost more; the median is optimal for absolute differences.
- For an even-length window either middle element works as the median; use one consistently.
Reference solution
Python
from typing import List
def maxFrequencyScore(nums: List[int], k: int) -> int:
a = sorted(nums)
n = len(a)
pre = [0] * (n + 1)
for i, v in enumerate(a):
pre[i + 1] = pre[i] + v
def cost(l: int, r: int) -> int:
m = (l + r) // 2
return a[m] * (m - l) - (pre[m] - pre[l]) + (pre[r + 1] - pre[m + 1]) - a[m] * (r - m)
best = 0
left = 0
for right in range(n):
while cost(left, right) > k:
left += 1
best = max(best, right - left + 1)
return bestJava
public static int maxFrequencyScore(int[] nums, int k) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
int best = 0, left = 0;
for (int right = 0; right < n; right++) {
while (true) {
int m = (left + right) / 2;
long cost = (long) a[m] * (m - left) - (pre[m] - pre[left]) + (pre[right + 1] - pre[m + 1]) - (long) a[m] * (right - m);
if (cost <= k) break;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}C++
int maxFrequencyScore(vector<int>& nums, int k) {
vector<int> a(nums.begin(), nums.end());
sort(a.begin(), a.end());
int n = a.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
int best = 0, left = 0;
for (int right = 0; right < n; right++) {
while (true) {
int m = (left + right) / 2;
long long cost = (long long) a[m] * (m - left) - (pre[m] - pre[left]) + (pre[right + 1] - pre[m + 1]) - (long long) a[m] * (right - m);
if (cost <= k) break;
left++;
}
best = max(best, right - left + 1);
}
return best;
}JavaScript
var maxFrequencyScore = function(nums, k) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var n = a.length;
var pre = [0];
for (var i = 0; i < n; i++) pre.push(pre[i] + a[i]);
var cost = function(l, r) {
var m = (l + r) >> 1;
return a[m] * (m - l) - (pre[m] - pre[l]) + (pre[r + 1] - pre[m + 1]) - a[m] * (r - m);
};
var best = 0, left = 0;
for (var right = 0; right < n; right++) {
while (cost(left, right) > k) left++;
if (right - left + 1 > best) best = right - left + 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