#3347

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Frequency of an Element After Performing Operations II

Determine the maximum frequency of any element after performing limited operations using binary search and sliding window techniques efficiently.

array binary search sliding window sorting prefix sum

Problem Statement

You are given an integer array nums and two integers k and numOperations. In each operation, you may increase or decrease an element by any value up to k. You must perform exactly numOperations operations distributed across any elements.

Return the maximum frequency of any element in nums achievable after completing all operations. Optimize your approach using sorting, prefix sums, and binary search to efficiently find the largest possible repeated element count.

Examples

Example 1

Input: nums = [1,4,5], k = 1, numOperations = 2

Output: 2

We can achieve a maximum frequency of two by:

Example 2

Input: nums = [5,11,20,20], k = 5, numOperations = 1

Output: 2

We can achieve a maximum frequency of two by:

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 109
0 <= numOperations <= nums.length

Solution Approach

Sort and Prepare Prefix Sums

Sort the array to structure potential target values. Build a prefix sum array to quickly calculate cumulative sums within any window, which allows checking if a range of elements can be adjusted to match a target value under k and numOperations constraints.

Binary Search Over Frequencies

Apply binary search on the possible frequency values. For each candidate frequency, check whether there exists a window of that length whose elements can all be converted to the same value using at most numOperations increments or decrements of up to k.

Sliding Window Validation

Slide a window of candidate frequency across the sorted array. Use prefix sums to compute the total operations needed to equalize elements within the window. If the required operations are within numOperations, record the frequency as achievable and continue searching for larger frequencies.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n), prefix sum construction is O(n). Each binary search step over frequencies is O(log n) with O(n) sliding window validation, giving overall O(n log n + n log n) time. Space is O(n) for sorting and prefix sums.

What Interviewers Usually Probe

You should consider binary search over the answer space rather than iterating naively.
Sliding window feasibility check will likely be a required optimization for large arrays.
Watch for integer overflows when summing large numbers multiplied by window size.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array first leads to incorrect window sums and invalid operation calculations.
Miscomputing the prefix sums can cause off-by-one errors when calculating required increments.
Failing to consider edge cases where k or numOperations are zero, potentially skipping valid maximum frequency.

Follow-up variants

Adjust operations to only allow increments, changing window validation slightly.
Allow k to vary per operation, requiring dynamic operation calculation in the sliding window.
Find maximum frequency after at most numOperations, making the problem slightly easier than exactly numOperations.

FAQ

What pattern does Maximum Frequency of an Element After Performing Operations II follow?

It uses binary search over the valid answer space combined with sliding window validation for achievable frequencies.

Can we use brute force to solve this problem?

Brute force is too slow due to high constraints; binary search with prefix sums is necessary for efficiency.

How do prefix sums help in this problem?

Prefix sums allow constant-time calculation of cumulative sums within a window, helping to quickly compute operations needed to equalize elements.

What if numOperations is zero?

The maximum frequency is simply the highest count of any number in the original array, as no modifications are allowed.

Why sort the array before applying operations?

Sorting ensures the sliding window covers consecutive values, which simplifies calculating the minimal operations needed to equalize elements.

terminal

Solution

Solution 1: Difference Array

According to the problem description, for each element $x$ in the array $\textit{nums}$, we can change it to any integer within the range $[x-k, x+k]$. We want to perform operations on some elements in $\textit{nums}$ to maximize the frequency of a certain integer in the array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        cnt = defaultdict(int)
        d = defaultdict(int)
        for x in nums:
            cnt[x] += 1
            d[x] += 0
            d[x - k] += 1
            d[x + k + 1] -= 1
        ans = s = 0
        for x, t in sorted(d.items()):
            s += t
            ans = max(ans, min(s, cnt[x] + numOperations))
        return ans

Continue Practicing

#3346 maximum frequency of an element after performing operations i #3413 maximum coins from k consecutive bags #2968 apply operations to maximize frequency score