You are given a 0-indexed integer array nums and an integer k.
You can perform the following operation on the array at most k times:
i from the array and increase or decrease nums[i] by 1.The score of the final array is the frequency of the most frequent element in the array.
Return the maximum score you can achieve.
The frequency of an element is the number of occurences of that element in the array.
Example 1:
Input: nums = [1,2,6,4], k = 3 Output: 3 Explanation: 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 Explanation: 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 <= 1051 <= nums[i] <= 1090 <= k <= 1014When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The values are ordered so that any group worth changing is a contiguous block. Every block length and every starting position is considered, and the cost of a block is the sum of its lower median minus each value in the block. A block is accepted when that signed cost is within the budget, and the longest accepted length is kept.
Here's how the algorithm would work step-by-step:
class Solution:
def maxFrequency(self, numbers, budget):
# Sorting the array is crucial because it allows us to consider contiguous subarrays as potential groups.
numbers.sort()
maximum_frequency_score = 0
number_of_elements = len(numbers)
# This outer loop iterates through all possible group sizes we could form.
for group_size in range(1, number_of_elements + 1):
# The inner loop checks every possible contiguous group of the current size.
for start_index in range(number_of_elements - group_size + 1):
end_index = start_index + group_size
current_group = numbers[start_index:end_index]
middle_index_in_group = (group_size - 1) // 2
target_value = current_group[middle_index_in_group]
total_cost = 0
for value in current_group:
total_cost += target_value - value
# If the cost is within budget, this group size is achievable.
if total_cost <= budget:
maximum_frequency_score = max(maximum_frequency_score, group_size)
# After checking all groups of all sizes, we have found the largest possible frequency.
return maximum_frequency_scoreAfter the same ordering, a window grows from the right and prefix sums make the cost of meeting the upper median available in constant time. The cost on the left of the median is the median times the left count minus the left sum, and the cost on the right is the right sum minus the median times the right count. Whenever the total exceeds the budget, the left end advances until the window fits, and the widest fitting window is the answer.
Here's how the algorithm would work step-by-step:
def maxFrequency(nums, k):
# Sorting allows us to consider contiguous subarrays as potential groups for modification.
nums.sort()
left_pointer = 0
max_frequency_found = 0
current_window_cost = 0
prefix_sums = [0]
for number in nums:
prefix_sums.append(prefix_sums[-1] + number)
for right_pointer in range(len(nums)):
current_window_size = right_pointer - left_pointer + 1
median_index = left_pointer + (current_window_size // 2)
median_value = nums[median_index]
# Cost is calculated based on the optimal strategy of making all elements equal to the median.
left_half_sum = prefix_sums[median_index] - prefix_sums[left_pointer]
right_half_sum = prefix_sums[right_pointer + 1] - prefix_sums[median_index + 1]
left_half_cost = (median_index - left_pointer) * median_value - left_half_sum
right_half_cost = right_half_sum - (right_pointer - median_index) * median_value
current_window_cost = left_half_cost + right_half_cost
# If the cost exceeds the budget, shrink the window from the left to find a valid subarray.
while current_window_cost > k:
left_pointer += 1
current_window_size = right_pointer - left_pointer + 1
if current_window_size <= 0:
break
median_index = left_pointer + (current_window_size // 2)
median_value = nums[median_index]
left_half_sum = prefix_sums[median_index] - prefix_sums[left_pointer]
right_half_sum = prefix_sums[right_pointer + 1] - prefix_sums[median_index + 1]
left_half_cost = (median_index - left_pointer) * median_value - left_half_sum
right_half_cost = right_half_sum - (right_pointer - median_index) * median_value
current_window_cost = left_half_cost + right_half_cost
max_frequency_found = max(max_frequency_found, right_pointer - left_pointer + 1)
return max_frequency_found| Case | How to Handle |
|---|---|
| The array contains one element | The frequency is one and the cost is zero, so the answer is one. |
| Every element is already equal | The whole array has cost zero and the answer is the length of the array. |
| The budget is zero and one value already repeats | A block of identical values costs nothing, so that run length is achievable. |
| The budget can pay for every element to meet one target | The longest affordable block can grow to the full length of the array. |
| A window costs more than the budget | The fast search drops elements from the left until the cost fits or the window is empty. |
| Equal values are scattered through the array | Sorting pulls nearby values together so a contiguous block can cover them. |