LeetCode 1838: Frequency of the Most Frequent Element

Explanation:

To solve this problem, we can use a sliding window approach. We will sort the input array nums and then maintain a window such that the sum of all elements within the window can be increased to meet the constraint of at most k operations. We will slide this window across the array while updating the sum and keeping track of the maximum frequency of an element within the window.

Here are the steps:

1. Sort the input array nums.
2. Initialize variables left and sum to track the left boundary of the window and the current sum within the window, respectively.
3. Iterate over the array using a right pointer:
   • Calculate the cost to make all elements within the window equal by multiplying the current number by its frequency and subtracting the sum of elements within the window.
   • While the cost exceeds k, increment the left pointer and update the sum accordingly.
   • Update the maximum frequency of an element found in the window.
4. Return the maximum frequency found.

Time complexity: O(nlogn) due to sorting the array where n is the length of the input array. Space complexity: O(1) since we are using constant extra space.

:

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