Frequency of the Most Frequent Element

• Sort the input array nums in non-decreasing order.
• To efficiently calculate the sum of elements in any subarray, precompute a prefix sum array. The prefix sum prefix[i] stores the sum of all elements from nums[0] to nums[i-1].
• Use a nested loop. The outer loop (j) fixes the right endpoint of the subarray (and thus the target value nums[j]), and the inner loop (i) iterates from j down to 0 to define the left endpoint.
• For each subarray nums[i...j], calculate the number of operations needed to make all its elements equal to nums[j]. The cost is (window_size * target_value) - window_sum, which translates to (long)(j - i + 1) * nums[j] - (prefix[j+1] - prefix[i]).
• If this cost is less than or equal to k, it means we can form a group of size j - i + 1. We update our maximum frequency found so far.
• If the cost exceeds k, we can break the inner loop for the current j, as extending the subarray to the left will only increase the cost.

First, we sort the input array nums. This is a key step because if we want to make a set of elements equal, it's always optimal to make them equal to the largest element in that set. After sorting, any such optimal set of elements will form a contiguous subarray.

To avoid re-calculating the sum of each subarray in the inner loop, we can pre-compute a prefix sum array. The prefix sum prefix[i] will store the sum of all elements from nums[0] to nums[i-1]. With this, the sum of any subarray nums[i...j] can be found in O(1) time by prefix[j+1] - prefix[i].

We then iterate through all possible subarrays using two nested loops. The outer loop with index j determines the right end of the subarray, making nums[j] the target value. The inner loop with index i determines the left end. For each subarray nums[i...j], we calculate the cost to make all its elements equal to nums[j]. The cost is the difference between the total value of the desired array (all elements are nums[j]) and the current sum of the subarray. This is (j - i + 1) * nums[j] - sum(nums[i...j]).

If the calculated cost is within our budget k, we have found a valid frequency of j - i + 1, and we update our overall maximum frequency. If the cost exceeds k, we can stop checking smaller i for the current j because making the subarray longer will only increase the cost.

1import java.util.Arrays;2 3class Solution {4    public int maxFrequency(int[] nums, int k) {5        Arrays.sort(nums);6        int n = nums.length;7        long[] prefixSum = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefixSum[i + 1] = prefixSum[i] + nums[i];10        }11 12        int maxFreq = 0;13        // Any single element has a frequency of at least 114        if (n > 0) maxFreq = 1;15 16        for (int j = 0; j < n; j++) {17            for (int i = 0; i < j; i++) {18                long windowSize = j - i + 1;19                long windowSum = prefixSum[j + 1] - prefixSum[i];20                long cost = windowSize * nums[j] - windowSum;21                if (cost <= k) {22                    maxFreq = Math.max(maxFreq, (int)windowSize);23                } else {24                    // Since the array is sorted, any window starting before i25                    // will also have a cost > k for the same endpoint j.26                    break; 27                }28            }29        }30        return maxFreq;31    }32}

• Sort the nums array.
• Create a prefix sum array prefix for O(1) window sum calculation.
• Initialize a search range for the answer: low = 1, high = n, and ans = 1.
• Perform a binary search on this range:
  • Calculate mid = low + (high - low) / 2. mid is the frequency we are checking.
  • Call a helper function isPossible(mid) to check if a frequency of mid is achievable within k operations.
  • If isPossible(mid) is true, it means a frequency of mid is possible. We store mid as a potential answer and try for a larger frequency by setting low = mid + 1.
  • If isPossible(mid) is false, mid is too large, so we search in the lower half by setting high = mid - 1.
• Return the final ans.

isPossible(len) function:

• Iterate through all windows of size len in the sorted nums array (from i = 0 to n - len).
• For each window nums[i...i+len-1], calculate the cost to make all elements equal to nums[i+len-1].
• The cost is (long)len * nums[i+len-1] - (prefix[i+len] - prefix[i]).
• If cost <= k for any window, return true immediately.
• If the loop finishes without finding such a window, return false.

The range of possible answers for the maximum frequency is from 1 to N. We can apply binary search on this answer space.

For a given frequency len that we want to test, we need an efficient way to check if it's possible to make len elements equal using at most k operations. This check is done in a helper function, isPossible(len).

First, we sort the nums array and precompute prefix sums. This setup allows the isPossible check to be performed efficiently. The isPossible(len) function iterates through all contiguous subarrays (windows) of size len in the sorted array. For each window, it calculates the cost to make all its elements equal to the largest element in that window (the rightmost one). The cost for a window nums[i...i+len-1] is len * nums[i+len-1] - sum(nums[i...i+len-1]). Using the prefix sum array, this sum is found in O(1). If this cost is <= k for any window, it means a frequency of len is achievable, and isPossible(len) returns true.

In the main binary search loop, if isPossible(mid) is true, we know mid is a valid frequency, so we record it and search for an even larger frequency in the right half of our search space (low = mid + 1). If it's false, mid is too high, and we must search for a smaller frequency in the left half (high = mid - 1).

1import java.util.Arrays;2 3class Solution {4    public int maxFrequency(int[] nums, int k) {5        Arrays.sort(nums);6        int n = nums.length;7        long[] prefixSum = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefixSum[i + 1] = prefixSum[i] + nums[i];10        }11 12        int low = 1, high = n;13        int ans = 1;14        while (low <= high) {15            int mid = low + (high - low) / 2;16            if (isPossible(mid, nums, k, prefixSum)) {17                ans = mid;18                low = mid + 1;19            } else {20                high = mid - 1;21            }22        }23        return ans;24    }25 26    private boolean isPossible(int len, int[] nums, int k, long[] prefixSum) {27        int n = nums.length;28        for (int i = 0; i <= n - len; i++) {29            int j = i + len - 1;30            long windowSum = prefixSum[j + 1] - prefixSum[i];31            long cost = (long)len * nums[j] - windowSum;32            if (cost <= k) {33                return true;34            }35        }36        return false;37    }38}

• Sort the array nums.
• Initialize a left pointer left = 0, a variable for the result maxFreq = 0, and a running sum currentSum = 0.
• Iterate through the array with a right pointer right from 0 to n-1:
  • Add nums[right] to currentSum to expand the window.
  • Check if the current window nums[left...right] is valid. The condition is (window_size * target_value) - window_sum <= k. This translates to (long)(right - left + 1) * nums[right] - currentSum <= k.
  • If the condition is violated (cost > k), shrink the window from the left: subtract nums[left] from currentSum and increment left. Repeat this in a while loop until the window becomes valid again.
  • After the while loop, the window nums[left...right] is the largest valid window ending at right. Update maxFreq = max(maxFreq, right - left + 1).
• After the loop finishes, return maxFreq.

This approach is based on the sliding window technique, which is highly efficient for problems involving contiguous subarrays. As with other approaches, the first step is to sort nums.

We use two pointers, left and right, to define the current window. The right pointer expands the window, and the left pointer shrinks it. We also maintain currentSum, the sum of elements within the window nums[left...right].

We iterate with the right pointer from the beginning to the end of the array. In each step, we add nums[right] to currentSum. Now, we have a new, larger window. We must check if this window is 'valid'. A window is valid if we can make all its elements equal to nums[right] (the largest element) using at most k operations. The cost for this is (window_size * nums[right]) - currentSum.

If this cost exceeds k, the window is invalid. We need to shrink it by moving the left pointer to the right. We subtract nums[left] from currentSum and increment left. We repeat this process until the window's cost is no longer greater than k.

After ensuring the window is valid, its size (right - left + 1) is a candidate for the maximum frequency. We update our answer, maxFreq, with the maximum size seen so far. Since the right pointer only moves forward, and the left pointer never moves backward, each element is processed a constant number of times, leading to a linear time complexity for the window traversal.

1import java.util.Arrays;2 3class Solution {4    public int maxFrequency(int[] nums, int k) {5        Arrays.sort(nums);6        int n = nums.length;7        int left = 0;8        int maxFreq = 0;9        long currentSum = 0;10 11        for (int right = 0; right < n; right++) {12            currentSum += nums[right];13            14            // Condition to check if the current window is valid.15            // We need (window size) * nums[right] - currentSum <= k16            while ((long)(right - left + 1) * nums[right] - currentSum > k) {17                currentSum -= nums[left];18                left++;19            }20            21            maxFreq = Math.max(maxFreq, right - left + 1);22        }23        24        return maxFreq;25    }26}