LeetCode Problem 2968

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sliding Window, Sorting, Prefix Sum

Solution

LeetCode 2968 - Apply Operations to Maximize Frequency Score

Problem Understanding

This problem asks us to maximize the frequency of the most common value in an array after performing at most k operations.

Each operation allows us to choose any element and either increase or decrease it by exactly 1. Since we can repeatedly apply operations to the same element, transforming a value a into a value b costs exactly |a - b| operations.

The key observation is that we are free to both increase and decrease values. Therefore, for any chosen group of elements, we can transform all of them into some common target value. The total cost is the sum of distances from each element to that target.

The score of the final array is simply the frequency of the most frequent element. Therefore, our goal is to find the largest subset of elements that can all be transformed into the same value using at most k operations.

The input size is large:

• n ≤ 100000
• nums[i] ≤ 10^9
• k ≤ 10^14

These constraints immediately rule out any solution that examines all subsets or performs expensive computations for every possible target.

An important mathematical fact is that for a set of numbers, the minimum total absolute distance is achieved when all numbers are moved to the median. This property will be the foundation of the optimal solution.

Several edge cases are worth noting:

• When k = 0, we cannot modify the array at all, so the answer is simply the maximum existing frequency.
• When all elements are already equal, the answer is n.
• Very large values of k may allow the entire array to be converted into a single value.
• Since nums[i] can be as large as 10^9 and k can reach 10^14, all cost calculations must use 64-bit integers.

Approaches

Brute Force

A brute-force approach would consider every possible subarray after sorting and determine whether all elements within that range can be converted into a common value using at most k operations.

For each range [l, r], we would compute the minimum cost of making all values equal. Since the optimal target is the median, we could find the median and calculate the total distance from every element in the range to that median.

There are O(n²) possible ranges. Even if cost computation were optimized, examining all ranges would still be far too slow for n = 100000.

Therefore, brute force is not feasible.

Key Insight

After sorting the array, any group of elements that will be transformed into the same value must correspond to a contiguous segment in sorted order.

Suppose we choose a sorted window [l, r].

To make all values equal, the optimal target is the median element of that window.

Therefore, the problem becomes:

Find the largest sorted window whose cost of converting all elements to its median is at most k.

This naturally suggests a sliding window approach.

The challenge is computing the cost of a window efficiently.

Using prefix sums, we can calculate the total distance to the median in O(1) time for any window.

Then a standard sliding window expands the right boundary and shrinks the left boundary whenever the cost exceeds k.

This yields an O(n log n) solution, where sorting dominates the complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Examines all possible ranges
Optimal	O(n log n)	O(n)	Sorting + sliding window + prefix sums

Algorithm Walkthrough

Step 1: Sort the Array

Sort nums.

After sorting, any set of elements that can be transformed into a common value optimally forms a contiguous segment.

Step 2: Build Prefix Sums

Create a prefix sum array:

prefix[i] = sum of first i elements

This allows us to obtain any range sum in constant time.

Step 3: Maintain a Sliding Window

Use two pointers:

left = 0
right = 0 ... n-1

The window [left, right] represents the current candidate group of elements that we want to transform into a common value.

Step 4: Find the Median

For a window:

mid = (left + right) // 2
median = nums[mid]

The median minimizes total absolute deviation.

Step 5: Compute Cost Using Prefix Sums

Split the window around the median.

For the left side:

costLeft =
median * (mid - left)
-
(sum of elements from left to mid-1)

For the right side:

costRight =
(sum of elements from mid+1 to right)
-
median * (right - mid)

The total cost is:

cost = costLeft + costRight

This computation takes O(1) time.

Step 6: Enforce the Budget

If:

cost > k

the current window is invalid.

Move left forward until the window becomes valid again.

Step 7: Update the Answer

Whenever the window is valid:

answer = max(answer, right - left + 1)

This tracks the largest feasible frequency.

Why it works

For any set of numbers, the median minimizes the sum of absolute distances. After sorting, every candidate group corresponds to a contiguous window. The sliding window always maintains the largest valid contiguous segment whose transformation cost does not exceed k. Since every possible valid segment is considered and costs are computed exactly, the maximum window size found is the maximum achievable frequency score.

Python Solution

from typing import List

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        def cost(left: int, right: int) -> int:
            mid = (left + right) // 2
            median = nums[mid]

            left_sum = prefix[mid] - prefix[left]
            left_cost = median * (mid - left) - left_sum

            right_sum = prefix[right + 1] - prefix[mid + 1]
            right_cost = right_sum - median * (right - mid)

            return left_cost + right_cost

        answer = 1
        left = 0

        for right in range(n):
            while cost(left, right) > k:
                left += 1

            answer = max(answer, right - left + 1)

        return answer

The implementation begins by sorting the array and constructing a prefix sum array. The helper function cost(left, right) computes the minimum number of operations required to make every element in the current window equal to its median.

The median index is computed directly from the window boundaries. Prefix sums allow the contribution from the left side and the right side to be calculated independently in constant time.

The sliding window expands by moving right. Whenever the current window exceeds the operation budget, the left pointer advances until the window becomes valid again.

The largest valid window size encountered during the process is returned as the answer.

Go Solution

func maxFrequencyScore(nums []int, k int64) int {
	sort.Ints(nums)

	n := len(nums)

	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(nums[i])
	}

	cost := func(left, right int) int64 {
		mid := (left + right) / 2
		median := int64(nums[mid])

		leftSum := prefix[mid] - prefix[left]
		leftCost := median*int64(mid-left) - leftSum

		rightSum := prefix[right+1] - prefix[mid+1]
		rightCost := rightSum - median*int64(right-mid)

		return leftCost + rightCost
	}

	ans := 1
	left := 0

	for right := 0; right < n; right++ {
		for cost(left, right) > k {
			left++
		}

		if right-left+1 > ans {
			ans = right - left + 1
		}
	}

	return ans
}

The Go implementation follows the same logic as the Python version.

The primary difference is that all arithmetic involving costs and prefix sums uses int64. This is necessary because values can reach approximately 10^14, which exceeds the range of a 32-bit integer.

The array is sorted using sort.Ints, and the prefix sums are stored in an []int64 slice to avoid overflow.

Worked Examples

Example 1

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

After sorting:

nums = [1,2,4,6]

Prefix sums:

Index	Prefix
0	0
1	1
2	3
3	7
4	13

Sliding Window Process

left	right	Window	Median	Cost	Valid
0	0	[1]	1	0	Yes
0	1	[1,2]	1	1	Yes
0	2	[1,2,4]	2	3	Yes
0	3	[1,2,4,6]	2	7	No
1	3	[2,4,6]	4	4	No
2	3	[4,6]	4	2	Yes

The largest valid window size encountered is:

3

Answer:

3

Example 2

nums = [1,4,4,2,4]
k = 0

After sorting:

nums = [1,2,4,4,4]

Prefix sums:

Index	Prefix
0	0
1	1
2	3
3	7
4	11
5	15

Sliding Window Process

left	right	Window	Cost
0	0	[1]	0
0	1	[1,2]	1
1	1	[2]	0
1	2	[2,4]	2
2	2	[4]	0
2	3	[4,4]	0
2	4	[4,4,4]	0

Largest valid window:

[4,4,4]

Size:

3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, sliding window is linear
Space	O(n)	Prefix sum array

The array is sorted once in O(n log n) time. After sorting, both pointers in the sliding window move monotonically from left to right, resulting in O(n) total window operations. Cost computation is O(1) due to prefix sums. Therefore the overall complexity is O(n log n).

The prefix sum array stores n + 1 values, giving O(n) auxiliary space usage.

Test Cases

sol = Solution()

assert sol.maxFrequencyScore([1, 2, 6, 4], 3) == 3  # provided example
assert sol.maxFrequencyScore([1, 4, 4, 2, 4], 0) == 3  # provided example

assert sol.maxFrequencyScore([5], 0) == 1  # single element
assert sol.maxFrequencyScore([7, 7, 7, 7], 0) == 4  # already equal
assert sol.maxFrequencyScore([1, 2], 1) == 2  # one operation enough

assert sol.maxFrequencyScore([1, 10], 8) == 1  # insufficient budget
assert sol.maxFrequencyScore([1, 10], 9) == 2  # exact budget

assert sol.maxFrequencyScore([1, 2, 3], 2) == 3  # convert all to 2
assert sol.maxFrequencyScore([1, 100, 200], 99) == 2  # only two can match

assert sol.maxFrequencyScore([1, 3, 5, 7, 9], 8) == 4  # larger window
assert sol.maxFrequencyScore([1, 1, 1000000000], 999999999) == 3  # large values

assert sol.maxFrequencyScore([2, 2, 2, 3, 3, 3], 0) == 3  # multiple modes
assert sol.maxFrequencyScore([1, 2, 3, 4, 5], 100) == 5  # huge budget

assert sol.maxFrequencyScore([1, 1, 2, 2, 3, 3], 2) == 4  # mixed duplicates

Test Summary

Test	Why
[1,2,6,4], k=3	Official example
[1,4,4,2,4], k=0	Official example with zero budget
[5]	Minimum array size
[7,7,7,7]	All values identical
[1,2], k=1	Exact cost for full conversion
[1,10], k=8	Budget just below requirement
[1,10], k=9	Budget exactly equal to requirement
[1,2,3], k=2	Entire array can become median
[1,100,200], k=99	Only partial conversion possible
[1,3,5,7,9], k=8	Larger sliding-window behavior
[1,1,1000000000], k=999999999	Very large values and costs
[2,2,2,3,3,3], k=0	Multiple existing modes
[1,2,3,4,5], k=100	Budget large enough for all elements
[1,1,2,2,3,3], k=2	Duplicate-heavy mixed case

Edge Cases

Zero Operations Available

When k = 0, no modifications are allowed. A common mistake is to assume some window can still be expanded through cost calculations. In reality, only windows whose cost is exactly zero are valid. The sliding window naturally handles this because any positive cost immediately forces the left boundary to move.

Very Large Numbers

The values of nums[i] can reach 10^9, and the total operation budget can reach 10^14. Using 32-bit arithmetic would overflow during prefix sum or cost calculations. The solution uses Python's arbitrary precision integers and int64 in Go to safely handle these values.

Even-Length Windows

For an even number of elements there are two medians. A common concern is whether choosing the lower median is always optimal. For absolute-distance minimization, any value between the two middle elements is optimal. Therefore using index (left + right) // 2 is sufficient and always yields the minimum possible cost.

Entire Array Becomes One Value

When k is very large, the optimal answer may be n. Some implementations incorrectly stop expanding after finding a large window. The sliding window continues examining all possibilities and therefore correctly returns the full array size whenever the total conversion cost is within budget.

Single-Element Windows

A window containing one element always has cost zero. This guarantees that the sliding window can always recover from an invalid larger window by shrinking until it becomes valid again. As a result, the algorithm never gets stuck and always maintains a valid window.