Maximum Frequency After K Increments

Problem

Given an array and an integer k, you may increment any element by 1, up to k total increments. Find the maximum possible frequency of any single element afterward.

Input:  nums = [1,2,4], k = 5
Output: 3   (raise 1 and 2 to 4, using 3+2=5 increments)

Python Solution

def max_frequency(nums, k):
    nums.sort()
    left = 0
    window_sum = 0
    best = 1
    for right in range(len(nums)):
        window_sum += nums[right]
        while nums[right] * (right - left + 1) - window_sum > k:
            window_sum -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

C++ Solution

int maxFrequency(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int left = 0, best = 1;
    long windowSum = 0;
    for (int right = 0; right < nums.size(); right++) {
        windowSum += nums[right];
        while ((long)nums[right] * (right - left + 1) - windowSum > k) {
            windowSum -= nums[left];
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Java Solution

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, best = 1;
        long windowSum = 0;
        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];
            while ((long) nums[right] * (right - left + 1) - windowSum > k) {
                windowSum -= nums[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n log n) — dominated by the initial sort; the sliding window pass itself is O(n). Space: O(log n) to O(n) depending on the sort implementation. Sorting first lets every window target raising all its elements up to the current rightmost (largest) value.