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 Window Prefix Sum

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Deutsche Bank PhonePe

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 <= 10⁵
1 <= nums[i] <= 10⁹
0 <= k <= 10¹⁴

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.

Sort the array: First, we sort nums in non-decreasing order. This costs O(N log N).
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.
Iterate Subarrays: We use two nested loops to consider every subarray nums[i...j].
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.
Update Maximum Frequency: If the cost is within our budget k, we update our answer with the current subarray's length.

1import java.util.Arrays;2 3class Solution {4    public int maxFrequencyScore(int[] nums, long k) {5        int n = nums.length;6        Arrays.sort(nums);7 8        long[] prefix = new long[n + 1];9        for (int i = 0; i < n; i++) {10            prefix[i + 1] = prefix[i] + nums[i];11        }12 13        int maxFreq = 0;14        if (n > 0) {15            maxFreq = 1;16        }17 18        for (int i = 0; i < n; i++) {19            for (int j = i + 1; j < n; j++) {20                int len = j - i + 1;21                int medianIndex = i + (len - 1) / 2;22                long medianValue = nums[medianIndex];23 24                // Cost for elements to the left of the median25                long leftSum = prefix[medianIndex] - prefix[i];26                long costLeft = medianValue * (long)(medianIndex - i) - leftSum;27 28                // Cost for elements to the right of the median29                long rightSum = prefix[j + 1] - prefix[medianIndex + 1];30                long costRight = rightSum - medianValue * (long)(j - medianIndex);31 32                if (costLeft + costRight <= k) {33                    maxFreq = Math.max(maxFreq, len);34                }35            }36        }37        return maxFreq;38    }39}

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.

A more efficient approach recognizes the monotonic nature of the problem. If we can achieve a frequency of f, we can certainly achieve any frequency smaller than f. This property allows us to binary search for the maximum possible frequency. The core of this approach is an efficient check function that determines if a given frequency is possible within the budget k.

Algorithm

The possible answer (maximum frequency) lies in the range [1, N].
We can binary search on this range to find the maximum frequency f.
For a given frequency f (our mid in the binary search), we need a function isPossible(f) to check if it's achievable.
isPossible(f) function:
- To check if a frequency of f is possible, we need to see if there's any contiguous subarray of length f in the sorted nums array that can be made uniform with at most k operations.
- We slide a window of fixed size f over the sorted array.
- For each window, we calculate the cost to change all its elements to its median. This is done in O(1) using a precomputed prefix sum array.
- If the cost for any window is <= k, we return true.
- If we check all windows and none satisfy the condition, we return false.
Based on the result of isPossible(mid):
- If true, a frequency of mid is possible, so we store it as a potential answer and try for a larger frequency (low = mid + 1).
- If false, mid is too large, so we search in the lower half (high = mid - 1).

Walkthrough

This approach transforms the problem from finding the maximum value to a series of decision problems.

Sort and Prefix Sums: Like the previous approach, we begin by sorting nums and creating a prefix sum array. These are done once.
Binary Search on Answer: We define a search space for the answer from 1 to N. We use binary search to find the largest value f in this range for which isPossible(f) is true.
Feasibility Check isPossible(f): This function checks if we can make f elements equal. It does this by iterating through all contiguous subarrays of length f in the sorted nums array. For each subarray (window), it calculates the cost to make all its elements equal to their median. If any window's cost is at most k, the function returns true.

This method is efficient because the feasibility check for a fixed window size f takes O(N) time, and we perform this check O(log N) times.

1import java.util.Arrays;2 3class Solution {4    public int maxFrequencyScore(int[] nums, long k) {5        int n = nums.length;6        Arrays.sort(nums);7 8        long[] prefix = new long[n + 1];9        for (int i = 0; i < n; i++) {10            prefix[i + 1] = prefix[i] + nums[i];11        }12 13        int low = 1, high = n, ans = 0;14        while (low <= high) {15            int mid = low + (high - low) / 2;16            if (isPossible(mid, nums, prefix, k)) {17                ans = mid;18                low = mid + 1;19            } else {20                high = mid - 1;21            }22        }23        return ans;24    }25 26    private boolean isPossible(int len, int[] nums, long[] prefix, long k) {27        if (len == 0) return true;28        int n = nums.length;29        for (int i = 0; i <= n - len; i++) {30            int j = i + len - 1;31            int medianIndex = i + (len - 1) / 2;32            long medianValue = nums[medianIndex];33 34            long leftSum = prefix[medianIndex] - prefix[i];35            long costLeft = medianValue * (long)(medianIndex - i) - leftSum;36 37            long rightSum = prefix[j + 1] - prefix[medianIndex + 1];38            long costRight = rightSum - medianValue * (long)(j - medianIndex);39 40            if (costLeft + costRight <= k) {41                return true;42            }43        }44        return false;45    }46}

Complexity

Time

O(N log N). Sorting takes `O(N log N)`. The binary search performs `O(log N)` iterations. Inside each, the `isPossible` check takes `O(N)` time. The total complexity is `O(N log N + N log N) = O(N log N)`.

Space

O(N) for the prefix sum array.

Trade-offs

Pros

Efficient O(N log N) time complexity, which passes the given constraints.
Binary search is a standard and powerful technique for problems with monotonic properties.

Cons

The implementation is more complex than a simple brute-force approach.
While having the same asymptotic time complexity as the sliding window approach, it might be slightly slower in practice due to the logarithmic factor from the binary search calls.

This is the most optimal approach, which uses a sliding window technique. After sorting the array, we maintain a window [left, right]. We expand the window by moving the right pointer and shrink it by moving the left pointer. The goal is to find the largest possible window for which the cost of making all its elements uniform (equal to their median) does not exceed k.

Algorithm

Sort the nums array and precompute the prefix sum array.
Initialize two pointers, left = 0 and right = 0, to represent the current window nums[left...right].
Initialize maxFreq = 0.
Iterate right from 0 to N-1 to expand the window.
For the current window [left, right], calculate the cost to make all its elements equal to their median.
If the cost > k, the window is too expensive. Shrink the window from the left by incrementing left until the cost is within the budget k.
Once the cost for the window [left, right] is valid (i.e., <= k), its length right - left + 1 is a possible frequency. Update maxFreq = max(maxFreq, right - left + 1).
Continue until right has traversed the entire array.

Walkthrough

This approach provides a linear-time scan over the sorted array, making it very efficient.

Sort and Prefix Sums: As with other approaches, we start by sorting nums and building a prefix sum array for O(1) cost calculations.
Sliding Window: We use two pointers, left and right, to define a window. The right pointer always moves forward, expanding the window. The left pointer moves forward only when the window needs to be shrunk.
Maintain Window Validity: For each position of right, we have a window [left, right]. We calculate the cost to unify this window's elements to their median. If this cost exceeds k, we know the window is too large. We then increment left, effectively sliding the window forward and shrinking it, and re-evaluate the cost. We repeat this until the cost for the window [left, right] is valid.
Update Max Frequency: At each step of the outer loop (for right), after we have adjusted left to form a valid window, the length right - left + 1 is the maximum possible frequency ending at right. We update our global maximum frequency with this length.

Because both left and right pointers only move forward, they each traverse the array at most once, leading to a linear time complexity for the windowing part.

1import java.util.Arrays;2 3class Solution {4    public int maxFrequencyScore(int[] nums, long k) {5        int n = nums.length;6        Arrays.sort(nums);7 8        long[] prefix = new long[n + 1];9        for (int i = 0; i < n; i++) {10            prefix[i + 1] = prefix[i] + nums[i];11        }12 13        int maxFreq = 0;14        int left = 0;15        for (int right = 0; right < n; right++) {16            // Keep shrinking the window from the left while the cost is too high17            while (calculateCost(left, right, nums, prefix) > k) {18                left++;19            }20            // The window [left, right] is now valid, update max frequency21            maxFreq = Math.max(maxFreq, right - left + 1);22        }23        return maxFreq;24    }25 26    private long calculateCost(int left, int right, int[] nums, long[] prefix) {27        int len = right - left + 1;28        int medianIndex = left + (len - 1) / 2;29        long medianValue = nums[medianIndex];30 31        long leftSum = prefix[medianIndex] - prefix[left];32        long costLeft = medianValue * (long)(medianIndex - left) - leftSum;33 34        long rightSum = prefix[right + 1] - prefix[medianIndex + 1];35        long costRight = rightSum - medianValue * (long)(right - medianIndex);36        37        return costLeft + costRight;38    }39}

Complexity

Time

O(N log N). Sorting takes `O(N log N)`. The sliding window part takes `O(N)` time because each pointer, `left` and `right`, traverses the array at most once. The total complexity is `O(N log N)`.

Space

O(N) for the prefix sum array.

Trade-offs

Pros

Highly efficient with O(N log N) time complexity, dominated by the initial sort.
Often faster in practice than the binary search approach due to better constant factors (a single pass after sorting).

Cons

The logic of calculating the cost for a dynamically changing window and ensuring correctness can be slightly more complex to grasp than the binary search approach.

Solutions

Solution

1class Solution {2public3  int maxFrequencyScore(int[] nums, long k) {4    Arrays.sort(nums);5    int n = nums.length;6    long[] s = new long[n + 1];7    for (int i = 1; i <= n; i++) {8      s[i] = s[i - 1] + nums[i - 1];9    }10    int l = 0, r = n;11    while (l < r) {12      int mid = (l + r + 1) >> 1;13      boolean ok = false;14      for (int i = 0; i <= n - mid; i++) {15        int j = i + mid;16        int x = nums[(i + j) / 2];17        long left = ((i + j) / 2 - i) * (long)x - (s[(i + j) / 2] - s[i]);18        long right = (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long)x);19        if (left + right <= k) {20          ok = true;21          break;22        }23      }24      if (ok) {25        l = mid;26      } else {27        r = mid - 1;28      }29    }30    return l;31  }32}

1class Solution {2public:3  int maxFrequencyScore(vector<int> &nums, long long k) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    vector<long long> s(n + 1, 0);7    for (int i = 1; i <= n; i++) {8      s[i] = s[i - 1] + nums[i - 1];9    }10    int l = 0, r = n;11    while (l < r) {12      int mid = (l + r + 1) >> 1;13      bool ok = false;14      for (int i = 0; i <= n - mid; i++) {15        int j = i + mid;16        int x = nums[(i + j) / 2];17        long long left =18            ((i + j) / 2 - i) * (long long)x - (s[(i + j) / 2] - s[i]);19        long long right =20            (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long long)x);21        if (left + right <= k) {22          ok = true;23          break;24        }25      }26      if (ok) {27        l = mid;28      } else {29        r = mid - 1;30      }31    }32    return l;33  }34};

1class Solution:2    def maxFrequencyScore(self, nums: List[int], k: int) -> int: nums . sort() s = list(accumulate(nums, initial=0)) n = len(nums) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 ok = False for i in range(n - mid + 1): j = i + mid x = nums[(i + j) // 2] left = ((i + j) // 2 - i) * x - (s[(i + j) // 2] - s[i]) right = (s[j] - s[(i + j) // 2]) - ((j - (i + j) // 2) * 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 problem

Solution

1class Solution {2public3  int maxFrequencyScore(int[] nums, long k) {4    Arrays.sort(nums);5    int n = nums.length;6    long[] s = new long[n + 1];7    for (int i = 1; i <= n; i++) {8      s[i] = s[i - 1] + nums[i - 1];9    }10    int l = 0, r = n;11    while (l < r) {12      int mid = (l + r + 1) >> 1;13      boolean ok = false;14      for (int i = 0; i <= n - mid; i++) {15        int j = i + mid;16        int x = nums[(i + j) / 2];17        long left = ((i + j) / 2 - i) * (long)x - (s[(i + j) / 2] - s[i]);18        long right = (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long)x);19        if (left + right <= k) {20          ok = true;21          break;22        }23      }24      if (ok) {25        l = mid;26      } else {27        r = mid - 1;28      }29    }30    return l;31  }32}

1class Solution {2public:3  int maxFrequencyScore(vector<int> &nums, long long k) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    vector<long long> s(n + 1, 0);7    for (int i = 1; i <= n; i++) {8      s[i] = s[i - 1] + nums[i - 1];9    }10    int l = 0, r = n;11    while (l < r) {12      int mid = (l + r + 1) >> 1;13      bool ok = false;14      for (int i = 0; i <= n - mid; i++) {15        int j = i + mid;16        int x = nums[(i + j) / 2];17        long long left =18            ((i + j) / 2 - i) * (long long)x - (s[(i + j) / 2] - s[i]);19        long long right =20            (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long long)x);21        if (left + right <= k) {22          ok = true;23          break;24        }25      }26      if (ok) {27        l = mid;28      } else {29        r = mid - 1;30      }31    }32    return l;33  }34};

1class Solution:2    def maxFrequencyScore(self, nums: List[int], k: int) -> int: nums . sort() s = list(accumulate(nums, initial=0)) n = len(nums) l, r = 0, n while l < r: mid = (l + r + 1) >> 1 ok = False for i in range(n - mid + 1): j = i + mid x = nums[(i + j) // 2] left = ((i + j) // 2 - i) * x - (s[(i + j) // 2] - s[i]) right = (s[j] - s[(i + j) // 2]) - ((j - (i + j) // 2) * x) if left + right <= k: ok = True break if ok: l = mid else: r = mid - 1 return l

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.