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

1
2
3
4
5
6
7
8

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

1
2
3

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 key idea is to maximize the frequency of any number by making as many elements equal to it as possible, using at most k operations. By sorting the array, we can efficiently use a sliding window to check, for each possible target value, how many elements can be converted to it within the allowed number of operations.

Approach

  1. Sort the array to bring similar numbers together.
  2. Use a sliding window:
  • For each right pointer, try to expand the window as much as possible such that the total cost to make all elements in the window equal to nums[right] does not exceed k.
  • The cost is calculated as the sum of differences between nums[right] and all elements in the window.
  1. If the cost exceeds k, move the left pointer to shrink the window.
  2. Track the maximum window size (i.e., frequency) achieved.
Step-by-step
  • Sort nums.
  • Initialize two pointers l and r, and a variable total to keep track of the sum of elements in the window.
  • For each r from 0 to n-1:
    • Add nums[r] to total.
    • While the cost to make all elements in the window equal to nums[r] exceeds k, move l right and subtract nums[l] from total.
    • Update the answer with the maximum window size (r - l + 1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
   int maxFrequency(vector<int>& nums, int k) {
      sort(nums.begin(), nums.end());
      long long total = 0;
      int l = 0, ans = 1;
      for (int r = 0; r < nums.size(); ++r) {
        total += nums[r];
        while ((long long)nums[r] * (r - l + 1) - total > k) {
           total -= nums[l++];
        }
        ans = max(ans, r - l + 1);
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
   public int maxFrequency(int[] nums, int k) {
      Arrays.sort(nums);
      long total = 0;
      int l = 0, ans = 1;
      for (int r = 0; r < nums.length; r++) {
        total += nums[r];
        while ((long)nums[r] * (r - l + 1) - total > k) {
           total -= nums[l++];
        }
        ans = Math.max(ans, r - l + 1);
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
   def maxFrequency(self, nums: list[int], k: int) -> int:
      nums.sort()
      total = 0
      l = 0
      ans = 1
      for r, val in enumerate(nums):
        total += val
        while val * (r - l + 1) - total > k:
           total -= nums[l]
           l += 1
        ans = max(ans, r - l + 1)
      return ans

Complexity

  • ⏰ Time complexity: O(N log N) (due to sorting and sliding window)
  • 🧺 Space complexity: O(1) (in-place, ignoring sort stack space)

Method 1 -

Code

Complexity

  • ⏰ Time complexity: O(nnnxxxnnn)
  • 🧺 Space complexity: O(nnnxxx)