Problem Statement in English

You’re given an integer array nums and an integer k. In one operation, you can choose an index of the array and increment the element at that index by 1. You can perform this operation at most k times.

Return the maximum possible frequency of an element after performing at most k operations.

Approach

To solve this problem, we can use a two-pointer technique (sliding window) along with sorting the array.

The idea is to maintain a window of elements that can be made equal to the current rightmost element in the window by using at most k increments. We will keep track of the sum of the elements in the current window and compare it with the required sum to make all elements in the window equal to the rightmost element. If the required increments exceed k, we will move the left pointer to shrink the window until we are within the allowed increments.

And we’re done!

Solution in Python


class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        l = currentSum = 0
        
        for r in range(len(nums)):
            currentSum += nums[r]
            
            if (r - l + 1) * nums[r] - currentSum > k:
                currentSum -= nums[l]
                l += 1
        
        return len(nums) - l

Complexity

  • Time: $O(n \log n)$
    Since we sort the array.

  • Space: $O(1)$
    Since we are using only constant space.

And we are done.