Taro Logo

Apply Operations to Maximize Frequency Score

Hard
Asked by:
Profile picture
17 views
Topics:
ArraysBinary SearchSliding WindowsGreedy Algorithms

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:

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

Solution


Clarifying Questions

When 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:

  1. Can each operation add one or subtract one from any chosen element?
  2. Is the score the frequency of the most common final value?
  3. Is a budget of zero allowed, leaving every element where it started?
  4. After the values are ordered, can the chosen elements form one contiguous block?
  5. May the shared target of a block be a median of that block?

Brute Force Solution

Approach

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:

  1. Sort the values into nondecreasing order.
  2. Try every block length from one through the full array.
  3. Slide a window of that length across the ordered values.
  4. Choose the lower median of the window as the target.
  5. Add the target minus each value to obtain the signed cost.
  6. Keep the length when the signed cost is within the budget.
  7. Return the largest length that was kept.

Code Implementation

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_score

Big(O) Analysis

Time Complexity
O(n^3) – Let n be the number of values. Sorting them is O(n log n) and is dominated by the later loops. There are n possible block lengths, and each length has O(n) starting positions. Scoring one window adds one term per element, which is proportional to the window length. Summing those window scores over every length and start produces O(n^3) time.
Space Complexity
O(1) – The values are reordered in the input array. The cost, the target, and the best length are a few scalars reused for every window. No second copy of a window is stored. The loops do not recurse. The extra memory is O(1).

Optimal Solution

Approach

After 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:

  1. Sort the values and build a prefix sum of the ordered array.
  2. Grow the right end of a window from the first value to the last.
  3. Place the median at the middle of the current window, rounding toward the right on an even length.
  4. Compute the left and right absolute deviations from that median with the prefix sums.
  5. Advance the left end while the combined cost is above the budget.
  6. Stop shrinking if the window would become empty.
  7. Record the larger of the best length so far and the current window length.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n log n) – Sorting the n values is O(n log n). The prefix sums are filled with one addition per value. The right end then advances once per value, and the left end also advances at most once per value across the whole scan. Each advance recomputes the median cost from the prefix sums in constant time. The linear scan is absorbed by the sort, so the total time is O(n log n).
Space Complexity
O(n) – The prefix array stores one sum for every prefix of the ordered values, plus a zero at the front, so it is proportional to n. The window indexes and the best length are scalars. Sorting reorders the input in place. No further tables are required. The extra memory is O(n).

Edge Cases

The array contains one element
How to Handle:
The frequency is one and the cost is zero, so the answer is one.
Every element is already equal
How to Handle:
The whole array has cost zero and the answer is the length of the array.
The budget is zero and one value already repeats
How to Handle:
A block of identical values costs nothing, so that run length is achievable.
The budget can pay for every element to meet one target
How to Handle:
The longest affordable block can grow to the full length of the array.
A window costs more than the budget
How to Handle:
The fast search drops elements from the left until the cost fits or the window is empty.
Equal values are scattered through the array
How to Handle:
Sorting pulls nearby values together so a contiguous block can cover them.