Scale Engineer

Apply Operations to Maximize Frequency Score

Hard
#2648Time: O(N^2). Sorting takes `O(N log N)`. The nested loops to iterate through all subarrays run in `O(N^2)`. Inside the loops, the cost calculation is `O(1)` thanks to prefix sums. The overall complexity is dominated by the nested loops.Space: O(N) to store the prefix sum array. If sorting is done in-place, it does not require extra space, otherwise it could be up to O(N) depending on the implementation.2 companies
Patterns
Sliding WindowPrefix Sum
Algorithms
Binary SearchSorting
Data structures
Array
Companies
Deutsche BankPhonePe

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible contiguous subarrays of the sorted input array. For each subarray, it calculates the minimum cost to make all its elements equal. The most efficient way to make a set of numbers equal is to change them all to their median. If this minimum cost is less than or equal to k, the length of that subarray is a possible frequency. We keep track of the maximum such length found.

Algorithm

  • Sort the input array nums.
  • Create a prefix sum array prefix to quickly calculate the sum of elements in any subarray. prefix[i] will store the sum of nums[0] to nums[i-1].
  • Initialize maxFreq = 0. If the array is not empty, the answer is at least 1.
  • Use nested loops to define the start i and end j of every possible contiguous subarray.
  • For each subarray nums[i...j]:
    • Calculate its length len = j - i + 1.
    • Find the median element, which for a sorted subarray is at index i + (len - 1) / 2.
    • Calculate the cost to make all elements in the subarray equal to the median value. This cost is the sum of differences: sum(|nums[k] - median|) for k from i to j. This can be computed in O(1) using the prefix sum array.
    • If the calculated cost is less than or equal to k, it means a frequency of len is achievable. Update maxFreq = max(maxFreq, len).
  • After checking all subarrays, maxFreq holds the result.

Walkthrough

The fundamental idea is that to achieve a frequency of f, we must choose f numbers from the array and make them identical. The cost of this operation is minimized if the chosen numbers are contiguous in the sorted version of the array, and the target value is their median.

This brute-force method systematically checks this for every possible contiguous subarray.

  1. Sort the array: First, we sort nums in non-decreasing order. This costs O(N log N).
  2. Prefix Sums: To avoid re-calculating sums for each subarray, we precompute a prefix sum array. prefix[i] will store the sum of nums[0]...nums[i-1]. This allows O(1) calculation of the sum of any subarray.
  3. Iterate Subarrays: We use two nested loops to consider every subarray nums[i...j].
  4. Calculate Cost: For each subarray, we find its median and calculate the cost to transform all its elements to that median. The cost for a subarray nums[i...j] with median m is (cost to raise elements smaller than m) + (cost to lower elements larger than m). With prefix sums, this is an O(1) operation.
  5. Update Maximum Frequency: If the cost is within our budget k, we update our answer with the current subarray's length.
import java.util.Arrays; class Solution {    public int maxFrequencyScore(int[] nums, long k) {        int n = nums.length;        Arrays.sort(nums);         long[] prefix = new long[n + 1];        for (int i = 0; i < n; i++) {            prefix[i + 1] = prefix[i] + nums[i];        }         int maxFreq = 0;        if (n > 0) {            maxFreq = 1;        }         for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int len = j - i + 1;                int medianIndex = i + (len - 1) / 2;                long medianValue = nums[medianIndex];                 // Cost for elements to the left of the median                long leftSum = prefix[medianIndex] - prefix[i];                long costLeft = medianValue * (long)(medianIndex - i) - leftSum;                 // Cost for elements to the right of the median                long rightSum = prefix[j + 1] - prefix[medianIndex + 1];                long costRight = rightSum - medianValue * (long)(j - medianIndex);                 if (costLeft + costRight <= k) {                    maxFreq = Math.max(maxFreq, len);                }            }        }        return maxFreq;    }}

Complexity

Time

O(N^2). Sorting takes `O(N log N)`. The nested loops to iterate through all subarrays run in `O(N^2)`. Inside the loops, the cost calculation is `O(1)` thanks to prefix sums. The overall complexity is dominated by the nested loops.

Space

O(N) to store the prefix sum array. If sorting is done in-place, it does not require extra space, otherwise it could be up to O(N) depending on the implementation.

Trade-offs

Pros

  • Relatively straightforward to understand and implement.

  • Correctly identifies the optimal substructure (contiguous subarrays in sorted array).

Cons

  • The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded (TLE) error.

Solutions

class Solution {public  int maxFrequencyScore(int[] nums, long k) {    Arrays.sort(nums);    int n = nums.length;    long[] s = new long[n + 1];    for (int i = 1; i <= n; i++) {      s[i] = s[i - 1] + nums[i - 1];    }    int l = 0, r = n;    while (l < r) {      int mid = (l + r + 1) >> 1;      boolean ok = false;      for (int i = 0; i <= n - mid; i++) {        int j = i + mid;        int x = nums[(i + j) / 2];        long left = ((i + j) / 2 - i) * (long)x - (s[(i + j) / 2] - s[i]);        long right = (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long)x);        if (left + right <= k) {          ok = true;          break;        }      }      if (ok) {        l = mid;      } else {        r = mid - 1;      }    }    return l;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem