Apply Operations to Maximize Frequency Score

Problem

You are given a 0-indexed integer array nums and an integer k.

You can perform the following operation on the array at most k times:

• Choose any index i from the array and increase or decrease nums[i] by 1.

The score of the final array is the frequency of the most frequent element in the array.

Return themaximum score you can achieve.

The frequency of an element is the number of occurences of that element in the array.

Examples

Example 1

Input: nums = [1,2,6,4], k = 3
Output: 3
Explanation: We can do the following operations on the array:
- Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3].
- Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2].
The element 2 is the most frequent in the final array so our score is 3.
It can be shown that we cannot achieve a better score.

Example 2

Input: nums = [1,4,4,2,4], k = 0
Output: 3
Explanation: We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k <= 1014

Solution

Method 1 – Sliding Window with Sorting

Intuition

The best value to make all elements in a window equal to (with minimal total absolute change) is the median of the window. After sorting the array, for any sliding window [l..r] the median index is med = (l + r + 1) / 2. When we add a new right element nums[r] the additional cost to make the window elements equal to the (possibly updated) median increases by nums[r] - nums[old_median]; when we remove the left element nums[l] the cost decreases by nums[old_median] - nums[l]. Using this incremental update with a sliding window and maintaining med lets us check feasibility against k in linear time.

Approach

• Sort nums to make contiguous windows meaningful.
• Use a sliding window [l..r] and maintain med = (l + r + 1) / 2 (integer division). Maintain a running cost that equals the total operations required to make all elements in [l..r] equal to nums[med].
• When extending the window with r++, increment cost by nums[r] - nums[old_med], then recompute med = (l + r + 1) / 2.
• While cost > k, advance l and decrement cost by nums[old_med] - nums[l], updating med after each move.
• Track maxFreq = max(maxFreq, r - l + 1) as the window expands.

This uses the median-based incremental update to avoid summing the whole window on every change.

Code

C++

class Solution {
public:
   int maxFrequencyScore(std::vector<int>& nums, long long k) {
      std::sort(nums.begin(), nums.end());
      int n = nums.size();
      int left = 0;
      int ans = 1;
      long long cost = 0;
      int medianIdx = 0;
      for (int right = 1; right < n; ++right) {
        cost += (long long)nums[right] - nums[medianIdx];
        medianIdx = (left + right + 1) / 2;
        while (cost > k) {
          cost -= (long long)nums[medianIdx] - nums[left];
          left++;
          medianIdx = (left + right + 1) / 2;
        }
        ans = std::max(ans, right - left + 1);
      }
      return ans;
   }
};

Java

class Solution {
  public int maxFrequencyScore(int[] nums, long k) {
    Arrays.sort(nums);
    int left = 0, ans = 1;
    long cost = 0;
    int medianIdx = 0;
    for (int right = 1; right < nums.length; right++) {
      cost += nums[right] - nums[medianIdx];
      medianIdx = (left + right + 1) / 2;
      while (cost > k) {
        cost -= nums[medianIdx] - nums[left];
        left++;
        medianIdx = (left + right + 1) / 2;
      }

      ans = Math.max(ans, right - left + 1);
    }

    return ans;
  }
}

Python

class Solution:
   def maxFrequencyScore(self, nums: list[int], k: int) -> int:
      nums.sort()
      n = len(nums)
      left = 0
      ans = 1
      cost = 0
      median_idx = 0
      for right in range(1, n):
        cost += nums[right] - nums[median_idx]
        median_idx = (left + right + 1) // 2
        while cost > k:
          cost -= nums[median_idx] - nums[left]
          left += 1
          median_idx = (left + right + 1) // 2
        ans = max(ans, right - left + 1)
      return ans

Complexity

• ⏰ Time complexity: O(N log N) — sorting dominates; the sliding-window pass is O(N).
• 🧺 Space complexity: O(1) — in-place (ignoring sort temporary space).