Apply Operations to Maximize Frequency Score - Solution & Explanation
Problem Statement
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:
- Choose any index
ifrom the array and increase or decreasenums[i]by1.
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 <= 1014
Approach Overview
Problem 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 1: Sliding Window and Two-pointer Technique
This approach uses a sliding window technique combined with sorting and a two-pointer mechanism to maximize frequency within the constraints of given operations. By setting a window, we gradually calculate the cost to equalize the elements to a candidate element. We carefully track the cost and adjust the window size to keep it within allowed operations (k).
The solution starts by sorting the array. We then use two pointers (left and right) to track the elements under consideration for increasing their frequency. The total_sum helps compute the total difference from the minimal cost to make all elements in the window equal to nums[right]. Whenever the cost exceeds k, the left pointer moves to reduce the window size.
Code
Python
Complexity
Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), using constant extra space.
Approach 2: Custom Frequency Analysis with Priority Handling
This solution involves calculating how many moves are needed to make every number in an array segment equal to a target value, continually adjusting this target to examine possible solutions. Unique numbers are processed by frequency and incremented/decremented based on cost, leveraging efficient priority management to keep track of operations required to balance the array.
By sorting and using two pointers, the code maintains a window of feasible size. The goal is to track the required sum increment to form that window into equal elements with a maximum count. Adjustments are made when necessary, rolled back by moving the left pointer, representing the boundary of the feasible range.
Code
C++
Complexity
Time Complexity: O(n log n) for sorting and O(n) for the two-pointer traversal.
Space Complexity: O(1), additional space is not used beyond constants.
Approach 3: Approach 1: Sliding Window
This approach utilizes a sliding window technique to find the maximum frequency possible by converting a contiguous segment of the array into the most frequent number possible under the constraints of given k operations.
The code sorts the array and uses two pointers to define a window. The right pointer extends the window and the left pointer adjusts it by removing elements until the window becomes valid under k operations. The largest valid window size is the solution.
Complexity
Time Complexity: O(n log n), due to the sorting step. Space Complexity: O(1), aside from input storage.
Approach 4: Approach 2: Binary Search + Prefix Sum
This approach combines binary search with prefix sums to efficiently compute potential frequency scores and compare them to k operations to find the feasible maximum frequency achievable.
This C code uses binary search to determine the maximum frequency feasible. It computes the necessary operations via prefix sums to decide if a given frequency is possible.
Complexity
Time Complexity: O(n log n), primarily due to the sorting step and binary search. Space Complexity: O(1), no additional data structures are utilized.
Approach 5: Sorting + Prefix Sum + Binary Search
The problem asks for the maximum frequency of the mode we can get after performing at most k operations. If we sort the array nums in ascending order, it would be best to turn a continuous segment of numbers into the same number, which can reduce the number of operations and increase the frequency of the mode.
Therefore, we might as well sort the array nums first.
Next, we analyze that if a frequency x is feasible, then for any y \le x, the frequency y is also feasible, which shows monotonicity. Therefore, we can use binary search to find the maximum feasible frequency.
We binary search the frequency, define the left boundary of the binary search as l = 0, and the right boundary as r = n, where n is the length of the array. In each binary search process, we take the middle value mid = \lfloor \frac{l + r + 1}{2} \rfloor, and then determine whether there exists a continuous subarray of length mid in nums, such that all elements in this subarray become the median of this subarray, and the number of operations does not exceed k. If it exists, then we update the left boundary l to mid, otherwise we update the right boundary r to mid - 1.
To determine whether such a subarray exists, we can use prefix sum. We first define two pointers i and j, initially i = 0, j = i + mid. Then all elements from nums[i] to nums[j - 1] are changed to nums[(i + j) / 2], and the number of operations required is left + right, where:
$
\begin{aligned}
left &= sum_{k = i}^{(i + j) / 2 - 1} (nums[(i + j) / 2] - nums[k]) \
&= ((i + j) / 2 - i) times nums[(i + j) / 2] - sum_{k = i}^{(i + j) / 2 - 1} nums[k]
\end{aligned}
\begin{aligned}
right &= sum_{k = (i + j) / 2 + 1}^{j} (nums[k] - nums[(i + j) / 2]) \
&= sum_{k = (i + j) / 2 + 1}^{j} nums[k] - (j - (i + j) / 2) times nums[(i + j) / 2]
\end{aligned}
We can use the prefix sum array s to calculate sum_{k = i}^{j} nums[k], so as to calculate left and right in O(1) time.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n$ is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window and Two-pointer Technique | Time Complexity: O(n log n), dominated by the sorting step. |
| Custom Frequency Analysis with Priority Handling | Time Complexity: O(n log n) for sorting and O(n) for the two-pointer traversal. |
| Approach 1: Sliding Window | Time Complexity: O(n log n), due to the sorting step. Space Complexity: O(1), aside from input storage. |
| Approach 2: Binary Search + Prefix Sum | Time Complexity: O(n log n), primarily due to the sorting step and binary search. Space Complexity: O(1), no additional data structures are utilized. |
| Sorting + Prefix Sum + Binary Search | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Apply Operations to Maximize Frequency Score | Weekly Contest 376 | Leetcode 2968 • codestorywithMIK • 6,221 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Apply Operations to Maximize Frequency Score easy or hard?
Apply Operations to Maximize Frequency Score Python/Java solution
How to solve Apply Operations to Maximize Frequency Score in O(n)?
What is the best approach for Apply Operations to Maximize Frequency Score?
Is Apply Operations to Maximize Frequency Score asked at Google/Amazon/Meta?
What data structure is used in Apply Operations to Maximize Frequency Score?
What is the time complexity of Apply Operations to Maximize Frequency Score?
Ready to solve this problem?
Practice Apply Operations to Maximize Frequency Score with our built-in code editor and test cases.
Practice on FleetCode