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]. nums becomes [1, 4, 5].nums[2]. 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] <= 1050 <= k <= 1050 <= numOperations <= nums.lengthProblem Overview: You are given an array and allowed to perform a limited number of operations where an element can be adjusted within a fixed range. The goal is to maximize how many elements can become equal to the same value after using at most numOperations. The challenge is identifying which value to target and how many nearby elements can be transformed to match it.
Approach 1: Sliding Window Technique (Sorting + Two Pointers) (Time: O(n log n), Space: O(1))
Start by sorting the array so elements close in value are adjacent. For a chosen target value, any number within the range [target - k, target + k] can potentially be converted to that value with one operation. Use a sliding window with two pointers to maintain a segment where the difference between the current element and the left boundary stays within 2 * k. This window represents values that can potentially converge to a single number. Track how many elements in the window already equal the target and how many require operations. If required operations exceed numOperations, shrink the window. This approach works well because sorting converts the range constraint into a contiguous window problem and allows efficient expansion and contraction using the sliding window pattern.
Approach 2: Binary Search with Prefix Sum (Time: O(n log n), Space: O(n))
Another strategy is to fix a candidate target and determine how many elements can be converted to it. After sorting the array, build a prefix sum array to quickly count elements in ranges. For each index, use binary search to find the boundaries of values within [nums[i] - k, nums[i] + k]. This gives the maximum set of numbers that could potentially become nums[i]. Some of them may already equal the target, while the rest require operations. Since only numOperations changes are allowed, the achievable frequency is existing + min(numOperations, convertible). Prefix sums help compute counts instantly, while binary search finds valid ranges in O(log n). The technique combines sorting, range queries, and binary search to efficiently evaluate each candidate value.
Recommended for interviews: The sliding window solution is typically preferred. It demonstrates strong pattern recognition and avoids repeated binary searches. Interviewers often expect candidates to sort the array and maintain a dynamic window of convertible values. The binary search + prefix sum method is still valid and shows a solid understanding of range queries and precomputation.
The sliding window technique can be utilized here to keep track of a window of elements that can be turned into the same value by using the allowed operations efficiently.
Sort the array first, then utilize a variable to track the cost of making elements within the current window equal. Expand the window while the cost is within the allowed operations, and shrink the window otherwise.
Here, we use a sliding window strategy. By sorting the input array, we calculate a cost to bring each window of elements to the same value by adding or subtracting using available operations. We adjust the window size effectively to stay within the given operations limit to maximize the frequency.
Time Complexity: O(n log n), due to the sorting operation. Space Complexity: O(1), as no extra space is used besides input sorting itself.
Another approach to solve this problem is using Binary Search combined with computing prefix sums. We attempt to make each element the highest frequency possible by using binary search on frequency and verify using prefix sum to ensure that allowed operations suffice to make all elements in range equal.
By prefix sum and binary search, checking the frequency transformable within the limit of allowed operations is done. This involves iterating through and checking transformations using the prefix sum accumulated to aid efficient calculation of needed operations per hypothetical frequency.
Time Complexity: O(n log m), where m is the max element - due to binary search. Space Complexity: O(n) for storing prefix sum.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window Technique | Time Complexity: O(n log n), due to the sorting operation. Space Complexity: O(1), as no extra space is used besides input sorting itself. |
| Approach 2: Binary Search with Prefix Sum | Time Complexity: O(n log m), where m is the max element - due to binary search. Space Complexity: O(n) for storing prefix sum. |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique | O(n log n) | O(1) | Best general solution after sorting; efficient when scanning contiguous convertible ranges |
| Binary Search with Prefix Sum | O(n log n) | O(n) | Useful when evaluating each element as a target with fast range counting |
Maximum Frequency of an Element After Performing Operations I | Made Easy | Leetcode 3346 • codestorywithMIK • 14,421 views views
Watch 9 more video solutions →Practice Maximum Frequency of an Element After Performing Operations I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor