Apply Operations to Maximize Frequency Score

Hard
1373.

Apply Operations to Maximize Frequency Score

Apply Operations to Maximize Frequency Score is a hard coding problem on arrays, sorting and prefix sum, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxFrequencyScore = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Hints for Apply Operations to Maximize Frequency Score

  1. 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.

  2. 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).

  3. 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

  1. Sort nums and build prefix sums P (64-bit).
  2. Define cost(l, r) with m = (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.
  3. Keep left = 0. For each right, advance left while cost(left, right) > k.
  4. 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 best

Java

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