3196. Apply Operations to Maximize Frequency Score
My accepted Python solution to LeetCode problem 3196, Apply Operations to Maximize Frequency Score, running in 835ms.
- Difficulty: Hard
- Python
- Runtime 835ms
- Memory 31.2MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 835ms, memory 31.2MB, accepted 2026-01-01.
class Solution:
def maxFrequencyScore(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
# Prefix sums for efficient range sum calculation
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
def cost(left, right):
# Cost to make all elements in [left, right] equal to median
mid = (left + right) // 2
median = nums[mid]
# Cost for left part (increase to median)
left_count = mid - left
left_sum = prefix[mid] - prefix[left]
left_cost = median * left_count - left_sum
# Cost for right part (decrease to median)
right_count = right - mid
right_sum = prefix[right + 1] - prefix[mid + 1]
right_cost = right_sum - median * right_count
return left_cost + right_cost
# Binary search for the maximum window size
def canAchieve(size):
for i in range(n - size + 1):
if cost(i, i + size - 1) <= k:
return True
return False
left, right = 1, n
result = 1
while left <= right:
mid = (left + right) // 2
if canAchieve(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result