#2968

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Apply Operations to Maximize Frequency Score

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

Maximize the frequency score by applying up to k operations on a sorted array using binary search over valid answer space.

array binary search sliding window sorting prefix sum

Problem Statement

You are given a 0-indexed integer array nums and an integer k. You can increase or decrease any element by 1 at most k total operations. Your goal is to maximize the frequency of the most frequent element in the resulting array.

Return the maximum possible frequency score after applying at most k operations. Constraints ensure large arrays and high operation counts, requiring efficient approaches like sorting, sliding window, and binary search over the valid answer space.

Examples

Example 1

Input: nums = [1,2,6,4], k = 3

Output: 3

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

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 <= 105
1 <= nums[i] <= 109
0 <= k <= 1014

Solution Approach

Sort the Array

Begin by sorting nums to allow contiguous subarrays to be equalized efficiently. Sorting ensures the sliding window can track ranges where the operations needed are minimal.

Sliding Window with Prefix Sum

Use a sliding window to maintain the sum of a subarray and calculate the total operations needed to make all elements equal to the largest in the window. Expand or shrink the window based on whether operations exceed k.

Binary Search Over Frequency

Apply binary search on the potential frequency score from 1 to nums.length. For each mid-value, check if a subarray can be equalized within k operations. This reduces the solution from O(n^2) to O(n log n).

Complexity Analysis

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

Time complexity is O(n log n) for sorting plus O(n) per binary search check, leading to O(n log n + n log n) overall. Space complexity is O(1) extra if using in-place prefix sums, otherwise O(n) for storing prefix sums.

What Interviewers Usually Probe

Notice that brute force O(n^2) checks will time out on large inputs.
Consider sorting first to simplify the operation calculations over subarrays.
Use binary search over the answer space to efficiently maximize frequency score.

Common Pitfalls or Variants

Common pitfalls

Forgetting that operations must be counted cumulatively, not per element.
Attempting to check every subarray without using sliding window optimization.
Not handling large k values correctly, which can exceed naive iteration limits.

Follow-up variants

Restrict operations to only increase values and see how the optimal subarray changes.
Find the minimum k needed to achieve a target frequency score instead of maximizing it.
Apply the same pattern but with modulo operations for cyclic value adjustments.

FAQ

What is the best approach for Apply Operations to Maximize Frequency Score?

Sort the array and use a sliding window to track subarrays while applying binary search over frequency scores to check feasibility.

Can we apply operations to decrease numbers as well as increase?

Yes, you can increase or decrease any element by 1 per operation, but the optimal strategy usually focuses on making a contiguous subarray equal.

Why is binary search over the answer space useful here?

Binary search efficiently narrows down the maximum frequency score achievable without testing every possible subarray explicitly.

How do we handle very large k values?

Use prefix sums with sliding window to calculate total operations needed for each subarray efficiently, ensuring correct handling of large k.

Is sorting necessary before applying operations?

Yes, sorting ensures the sliding window can cover contiguous elements optimally, which is key to maximizing frequency score efficiently.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        s = list(accumulate(nums, initial=0))
        n = len(nums)
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            ok = False
            for i in range(n - mid + 1):
                j = i + mid
                x = nums[(i + j) // 2]
                left = ((i + j) // 2 - i) * x - (s[(i + j) // 2] - s[i])
                right = (s[j] - s[(i + j) // 2]) - ((j - (i + j) // 2) * x)
                if left + right <= k:
                    ok = True
                    break
            if ok:
                l = mid
            else:
                r = mid - 1
        return l

Continue Practicing

#3346 maximum frequency of an element after performing operations i #3347 maximum frequency of an element after performing operations ii #3413 maximum coins from k consecutive bags