Code Implementation

class Solution:
    def maxFrequency(self, nums, k):
        nums.sort()
        l = 0
        total = 0
        res = 1
        for r in range(len(nums)):
            total += nums[r]
            # window size = r - l + 1
            # total increases by k at most
            while (nums[r] * (r - l + 1)) - total > k:
                total -= nums[l]
                l += 1
            res = max(res, r - l + 1)
        return res
      

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long total = 0;
        int res = 1, l = 0;
        for (int r = 0; r < nums.size(); ++r) {
            total += nums[r];
            while ((long long)nums[r] * (r - l + 1) - total > k) {
                total -= nums[l];
                l++;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};
      

import java.util.Arrays;
class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        long total = 0;
        int l = 0, res = 1;
        for (int r = 0; r < nums.length; r++) {
            total += nums[r];
            while ((long)nums[r] * (r - l + 1) - total > k) {
                total -= nums[l];
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}
      

var maxFrequency = function(nums, k) {
    nums.sort((a, b) => a - b);
    let l = 0, total = 0, res = 1;
    for (let r = 0; r < nums.length; r++) {
        total += nums[r];
        while (nums[r] * (r - l + 1) - total > k) {
            total -= nums[l];
            l++;
        }
        res = Math.max(res, r - l + 1);
    }
    return res;
};
      

Problem Description

You are given an integer array nums and an integer k. In one operation, you can increment any element of nums by 1. Your goal is to maximize the frequency of any element in the array (that is, the number of times a value appears) by performing at most k total increment operations (across any elements).

Return the maximum possible frequency of any element after performing at most k operations. Each increment operation can be applied to any element, and you can increment the same element multiple times. You cannot decrement any element.

Constraints:

• There is always at least one valid solution.
• Elements may be reused as many times as needed for increments.
• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁵
• 1 ≤ k ≤ 10⁹

Thought Process

At first glance, it might seem natural to try every possible way of incrementing elements to make as many of them equal as possible. For example, you could try to pick a value in nums and use your k increments to make as many other elements as possible match it. However, this would be computationally expensive, especially for large arrays.

To optimize, we notice that making elements equal to a larger value will generally require more increments. Therefore, it's more efficient to focus on making elements equal to some value by incrementing smaller numbers up to it. By sorting the array, we can consider for each position: "How many elements to the left can I increment up to match this value, given my limited k?".

This leads to a sliding window approach, where we try to maintain a window (subarray) where all elements can be incremented to match the rightmost value, using at most k operations. The window slides forward as we find that the cost exceeds k.

Solution Approach

• Step 1: Sort the Array
  • Sorting makes it easier to increment smaller elements to match a larger value, and to analyze the cost of such increments efficiently.
• Step 2: Sliding Window
  • Use two pointers (l and r) to represent the current window.
  • For each new element at r, calculate the total number of increments needed to bring all elements in nums[l..r] up to nums[r].
  • This cost is nums[r] * (r - l + 1) - sum(nums[l..r]).
  • If the cost exceeds k, move l to the right and subtract nums[l] from the running sum, until the cost is within k.
• Step 3: Track the Maximum Window Size
  • For each window where the cost is within k, update the result with the window's size, which represents the frequency of the most frequent element achievable.
• Step 4: Return the Result
  • After processing all elements, return the largest window size found.

This approach is efficient because sorting is O(n log n), and the sliding window processes each element at most twice, for an overall time complexity of O(n log n).

Example Walkthrough

Let's walk through an example with nums = [1, 2, 4] and k = 5.

1. Sort nums: [1, 2, 4]
2. Initialize: l = 0, total = 0, res = 1
3. r = 0:
   • total = 1
   • cost = 1 * 1 - 1 = 0 ≤ 5
   • res = max(1, 1) = 1
4. r = 1:
   • total = 1 + 2 = 3
   • cost = 2 * 2 - 3 = 1 ≤ 5
   • res = max(1, 2) = 2
5. r = 2:
   • total = 3 + 4 = 7
   • cost = 4 * 3 - 7 = 5 ≤ 5
   • res = max(2, 3) = 3
6. End: The answer is 3. We can increment 1 and 2 both up to 4 (using 3 + 2 = 5 increments), so all elements become 4.

Time and Space Complexity

• Brute-force Approach:
  • For each unique value, we could try to bring all smaller elements up to it, checking the cost each time. This would be O(n^2) in the worst case, which is too slow for large n.
• Optimized Sliding Window Approach:
  • Sorting the array: O(n log n)
  • Sliding window: Each element is added and removed from the window at most once, so O(n)
  • Total time: O(n log n)
  • Space: O(1) extra (excluding sort), or O(n) if sort is not in-place.

Summary

The key insight for this problem is to use a sliding window over the sorted array, efficiently tracking the minimal cost to make a group of elements equal to the largest in the window. By maintaining a running sum and adjusting the window when the cost exceeds k, we find the largest possible frequency achievable with the allowed number of increments. This approach is both elegant and efficient, scaling well even for large input sizes.