# Apply Operations to Maximize Frequency Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/apply-operations-to-maximize-frequency-score)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-maximize-frequency-score
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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
## Brute Force with Prefix Sums
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Binary Search on Frequency
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`.
**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.
**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.
### Explanation
This approach transforms the problem from finding the maximum value to a series of decision problems.

1.  **Sort and Prefix Sums**: Like the previous approach, we begin by sorting `nums` and creating a prefix sum array. These are done once.
2.  **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.
3.  **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.

```java
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 low = 1, high = n, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(mid, nums, prefix, k)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int len, int[] nums, long[] prefix, long k) {
        if (len == 0) return true;
        int n = nums.length;
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            int medianIndex = i + (len - 1) / 2;
            long medianValue = nums[medianIndex];

            long leftSum = prefix[medianIndex] - prefix[i];
            long costLeft = medianValue * (long)(medianIndex - i) - leftSum;

            long rightSum = prefix[j + 1] - prefix[medianIndex + 1];
            long costRight = rightSum - medianValue * (long)(j - medianIndex);

            if (costLeft + costRight <= k) {
                return true;
            }
        }
        return false;
    }
}
```
### 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`).

## Optimal Sliding Window
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`.
**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.
**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.
### Explanation
This approach provides a linear-time scan over the sorted array, making it very efficient.

1.  **Sort and Prefix Sums**: As with other approaches, we start by sorting `nums` and building a prefix sum array for `O(1)` cost calculations.
2.  **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.
3.  **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.
4.  **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.

```java
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;
        int left = 0;
        for (int right = 0; right < n; right++) {
            // Keep shrinking the window from the left while the cost is too high
            while (calculateCost(left, right, nums, prefix) > k) {
                left++;
            }
            // The window [left, right] is now valid, update max frequency
            maxFreq = Math.max(maxFreq, right - left + 1);
        }
        return maxFreq;
    }

    private long calculateCost(int left, int right, int[] nums, long[] prefix) {
        int len = right - left + 1;
        int medianIndex = left + (len - 1) / 2;
        long medianValue = nums[medianIndex];

        long leftSum = prefix[medianIndex] - prefix[left];
        long costLeft = medianValue * (long)(medianIndex - left) - leftSum;

        long rightSum = prefix[right + 1] - prefix[medianIndex + 1];
        long costRight = rightSum - medianValue * (long)(right - medianIndex);
        
        return costLeft + costRight;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxFrequencyScore(vector<int> &nums, long long k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<long long> s(n + 1, 0);
    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;
      bool ok = false;
      for (int i = 0; i <= n - mid; i++) {
        int j = i + mid;
        int x = nums[(i + j) / 2];
        long long left =
            ((i + j) / 2 - i) * (long long)x - (s[(i + j) / 2] - s[i]);
        long long right =
            (s[j] - s[(i + j) / 2]) - ((j - (i + j) / 2) * (long long)x);
        if (left + right <= k) {
          ok = true;
          break;
        }
      }
      if (ok) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    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

```