Watch 6 video solutions for Apply Operations to Maximize Frequency Score, a hard level problem involving Array, Binary Search, Sliding Window. This walkthrough by codestorywithMIK has 5,610 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums and an integer k.
You can perform the following operation on the array at most k times:
i from the array and increase or decrease nums[i] by 1.The score of the final array is the frequency of the most frequent element in the array.
Return the maximum score you can achieve.
The frequency of an element is the number of occurences of that element in the array.
Example 1:
Input: nums = [1,2,6,4], k = 3 Output: 3 Explanation: We can do the following operations on the array: - Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2]. The element 2 is the most frequent in the final array so our score is 3. It can be shown that we cannot achieve a better score.
Example 2:
Input: nums = [1,4,4,2,4], k = 0 Output: 3 Explanation: We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1014Problem Overview: You are given an array and a limit on operations. Each operation increases an element, and the goal is to maximize the frequency score of equal values after performing at most k operations. The challenge is determining the largest group of numbers that can be adjusted to the same value without exceeding the operation budget.
Approach 1: Sliding Window (Sorting + Cost Tracking) (Time: O(n log n), Space: O(1))
Sort the array so values grow monotonically. Then use a classic two‑pointer sliding window. The right pointer expands the window while the left pointer shrinks it when the cost exceeds k. The key idea: if you want all numbers in the window to match nums[right], the cost equals nums[right] * window_size - window_sum. Maintain the running sum of the window to compute this efficiently. This approach avoids recomputation and finds the maximum valid window length in linear time after sorting.
Approach 2: Binary Search + Prefix Sum (Time: O(n log n), Space: O(n))
Another way is to binary search the answer (the maximum achievable frequency). After sorting, precompute a prefix sum array to query sums quickly. For a candidate frequency f, check every window of size f. The target value becomes the largest element in the window, and the cost to raise all other values is computed using the prefix sums. If the required operations stay within k, that frequency is feasible. Binary search narrows down the maximum valid frequency.
Approach 3: Custom Frequency Analysis with Priority Handling (Time: O(n log n), Space: O(n))
This strategy maintains candidate values and dynamically tracks the cost of aligning nearby elements. A priority or ordered structure helps determine which elements require the least incremental operations. The algorithm gradually grows candidate groups while maintaining the operation budget. While more complex, this method can be useful when experimenting with dynamic grouping or extending the logic to streaming scenarios.
Recommended for interviews: The Sliding Window solution is usually what interviewers expect. Sorting combined with a two‑pointer window shows strong understanding of cost aggregation and greedy expansion. The Binary Search + Prefix Sum approach demonstrates deeper algorithmic thinking and is useful when the feasibility of a window size must be checked repeatedly. Relevant techniques include array processing, sliding window, binary search, and prefix sum.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window (Sorting + Two Pointers) | O(n log n) | O(1) | Best practical solution after sorting; efficient for large arrays |
| Binary Search + Prefix Sum | O(n log n) | O(n) | Useful when validating candidate frequency sizes or practicing feasibility checks |
| Custom Frequency Analysis with Priority Handling | O(n log n) | O(n) | Exploring dynamic grouping strategies or more flexible frequency tracking |