You are given an integer array nums and two integers k and numOperations.
You must perform an operation numOperations times on nums, where in each operation you:
i that was not selected in any previous operations.[-k, k] to nums[i].Return the maximum possible frequency of any element in nums after performing the operations.
Example 1:
Input: nums = [1,4,5], k = 1, numOperations = 2
Output: 2
Explanation:
We can achieve a maximum frequency of two by:
nums[1], after which nums becomes [1, 4, 5].nums[2], after which nums becomes [1, 4, 4].Example 2:
Input: nums = [5,11,20,20], k = 5, numOperations = 1
Output: 2
Explanation:
We can achieve a maximum frequency of two by:
nums[1].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1090 <= numOperations <= nums.lengthProblem Overview: You are given an array where operations can adjust values within a certain range. The goal is to maximize the frequency of a single element after performing at most k operations. Each operation allows modifying values so that multiple elements can be aligned to the same target value.
The challenge is determining which value should become the target and how many surrounding elements can be transformed into it while staying within the allowed operation budget. Efficient solutions rely on sorting, range counting, and window-based cost tracking.
Approach 1: Sliding Window Technique (Sorting + Prefix Cost Tracking) (Time: O(n log n), Space: O(1))
Sort the array so values are processed in increasing order. Once sorted, treat each value as a potential target and expand a sliding window that represents elements you want to convert to this target. As the right pointer grows, compute the cost required to raise all elements in the window to match the current value. If the cost exceeds the allowed operations, shrink the window from the left.
The key insight: after sorting, the cheapest way to increase frequency is to raise smaller elements toward a larger target. Maintaining a running window lets you check feasibility in constant time per step. This approach combines sorting with a classic sliding window pattern to efficiently track the maximum achievable frequency.
Approach 2: Greedy with Frequency Count (Binary Search + Prefix Sum) (Time: O(n log n), Space: O(n))
This method focuses on evaluating each unique value as a potential target. After sorting the array, build prefix sums so the cost of converting a range can be computed instantly. For each index, use binary search to determine the farthest left boundary where the cost to convert all numbers to the current value does not exceed the allowed operations.
The prefix sums allow quick computation of the total increments required to raise a subarray to the target value. Greedy reasoning ensures that expanding toward smaller values gives the largest possible group. This approach blends prefix sum range calculations with binary search to efficiently test valid windows.
Recommended for interviews: The sliding window solution is typically expected. It demonstrates strong understanding of sorted array properties, two‑pointer window expansion, and incremental cost maintenance. A brute force approach would check every possible target and range, which quickly becomes quadratic. Showing that baseline reasoning helps, but implementing the optimized sliding window proves algorithmic maturity.
This approach leverages a sorted array and the sliding window approach to maximize the frequency of elements. The idea is to use the sliding window to keep track of a subarray where you can potentially make all elements equal by performing add operations within the given range [-k, k].
You maintain a window that only expands when the needed operations are within the limit specified by numOperations. This involves checking the operations needed to turn the smallest element in the window into the largest element and adjusting it as necessary to stretch the window.
The C code uses quick-sort to sort the array and then applies a sliding window to calculate the maximum frequency of any number that can be achieved by performing operations. The steps:
left and right to maintain the window.right pointer index and adjust the left pointer accordingly.C
Python
Java
C#
JavaScript
Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array.
Space Complexity: O(1) because modification is done in place.
This approach focuses on efficiently maximizing the frequency using a greedy strategy with a series of modifications limited by numOperations. It involves selectively manipulating elements to bunch them toward an optimal frequency level after sorting the array.
The process aims to utilize available changes strategically for maximizing occurrences of a particular value obtained.
The C++ code example applies sorting followed by greedy decision making:
k.C++
JavaScript
Time Complexity: O(n log n) due to sort operation as largest part.
Space Complexity: O(1) as changes are internal within the input collection.
According to the problem description, for each element x in the array nums, we can change it to any integer within the range [x-k, x+k]. We want to perform operations on some elements in nums to maximize the frequency of a certain integer in the array.
The problem can be transformed into merging all elements in the interval [x-k, x+k] corresponding to each element x, and finding the integer that contains the most original elements in the merged intervals. This can be implemented using a difference array.
We use a dictionary d to record the difference array. For each element x, we perform the following operations on the difference array:
1 at position x-k, indicating that a new interval starts from this position.1 at position x+k+1, indicating that an interval ends from this position.0 at position x, ensuring that position x exists in the difference array for subsequent calculations.At the same time, we need to record the number of occurrences of each element in the original array, using a dictionary cnt to implement this.
Next, we perform prefix sum calculation on the difference array to get how many intervals cover each position. For each position x, we calculate the number of intervals covering it as s. Then we discuss by cases:
x appears in the original array, operations on x itself are meaningless. Therefore, there are s - cnt[x] other elements that can be changed to x through operations, but at most numOperations operations can be performed. So the maximum frequency at this position is cnt[x] + min(s - cnt[x], numOperations).x does not appear in the original array, then at most numOperations operations can be performed to change other elements to x. Therefore, the maximum frequency at this position is min(s, numOperations).Combining the above two cases, we can uniformly express it as min(s, cnt[x] + numOperations).
Finally, we traverse all positions, calculate the maximum frequency at each position, and take the maximum value among them as the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n log n) due to sorting, where n is the number of elements in the array. Space Complexity: O(1) because modification is done in place. |
| Greedy with Frequency Count | Time Complexity: O(n log n) due to sort operation as largest part. Space Complexity: O(1) as changes are internal within the input collection. |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique (Sorted Array) | O(n log n) | O(1) | Best general solution after sorting. Efficient for large arrays and common interview expectation. |
| Greedy with Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when prefix sums are already available or when analyzing valid ranges via binary search. |
| Naive Range Checking (Conceptual Baseline) | O(n^2) | O(1) | Only helpful for understanding the brute force idea before optimizing. |
3347 & 3346. Maximum Frequency of an Element After Performing Operations II Line Sweep • Aryan Mittal • 11,002 views views
Watch 9 more video solutions →Practice Maximum Frequency of an Element After Performing Operations II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor