# Maximum Frequency of an Element After Performing Operations II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-frequency-of-an-element-after-performing-operations-ii
**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
---
## Problem
You are given an integer array `nums` and two integers `k` and `numOperations`.

You must perform an **operation** `numOperations` times on `nums`, where in each operation you:

* Select an index `i` that was **not** selected in any previous operations.
* Add an integer in the range `[-k, k]` to `nums[i]`.

Return the **maximum** possible frequency of any element in `nums` after performing the **operations**.

**Example 1:**

**Input:** nums = \[1,4,5\], k = 1, numOperations = 2

**Output:** 2

**Explanation:**

We can achieve a maximum frequency of two by:

* Adding 0 to `nums[1]`, after which `nums` becomes `[1, 4, 5]`.
* Adding -1 to `nums[2]`, after which `nums` becomes `[1, 4, 4]`.

**Example 2:**

**Input:** nums = \[5,11,20,20\], k = 5, numOperations = 1

**Output:** 2

**Explanation:**

We can achieve a maximum frequency of two by:

* Adding 0 to `nums[1]`.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `0 <= k <= 109`
* `0 <= numOperations <= nums.length`

# Approaches
## Brute Force over Subarrays
This approach involves systematically checking every possible contiguous subarray within the sorted `nums` array. For each subarray, we evaluate if all its elements can be unified into a single target value, given the constraints on operations. The core idea is that if a group of `m` elements can be made equal, they must form a subsequence where the difference between the maximum and minimum element is at most `2*k`. By sorting the array, we can focus on contiguous subarrays as candidates for such groups. For each subarray, we then try to find a suitable target value `T` among its own elements that minimizes the number of required operations and satisfies all problem conditions.
**Time:** O(N^3) or O(N^2) with optimizations. Sorting takes O(N log N). The nested loops run in O(N^2). Inside the inner loop, iterating through the window to test targets takes O(N) time, leading to O(N^3). This can be optimized to O(N^2) by efficiently querying counts, but it's still too slow for the given constraints. · **Space:** O(N) in the worst case for the frequency map within the loops.
**Pros:** It's a straightforward, brute-force-like approach that correctly explores the problem space based on the sorted array property.; It's easier to reason about and implement compared to more optimized and complex solutions.
**Cons:** The time complexity of O(N^2) can be too slow for the given constraints (N up to 10^5), likely resulting in a 'Time Limit Exceeded' error.
### Explanation
First, we sort the array `nums` to easily handle the condition `max - min <= 2*k`. After sorting, any subsequence that can be unified will be contained within a contiguous block `nums[i...j]` where `nums[j] - nums[i] <= 2*k`.

We use nested loops to consider every contiguous subarray `nums[i...j]`. For each subarray, we check if it's a candidate for unification. The length of this subarray, `m = j - i + 1`, is a potential frequency we can achieve.

To unify the elements of `nums[i...j]`, we need a target `T`. A valid `T` must be reachable from every element in the subarray, meaning `|T - nums[k]| <= k` for all `k` from `i` to `j`. This is possible if and only if there's an overlap in the possible ranges, which simplifies to `nums[j] - nums[i] <= 2*k`.

Assuming this holds, we need to find a `T` that satisfies the operation constraints. The number of operations depends on how many elements are already equal to `T`. To minimize operations, we should choose a `T` that is already frequent in the subarray. The best candidates for `T` are the elements `x` present in `nums[i...j]`. For each such `x`, we check if it's a valid target for the whole subarray (`max(x - nums[i], nums[j] - x) <= k`). If it is, we count its occurrences `c` and check if the number of modifications `m-c` is within our budget (`m-c <= numOperations`) and if the leftover operations can be used on other elements (`numOperations + c <= nums.length`). If we find such a valid configuration, we update our maximum frequency found so far.

To implement this, we can use a frequency map for each window to count occurrences, leading to an overall `O(N^2)` complexity.

```java
import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        int n = nums.length;
        Arrays.sort(nums);
        int maxFreq = 0;

        // Find initial frequency for the case of 0 operations
        if (n > 0) {
            int currentStreak = 1;
            maxFreq = 1;
            for (int i = 1; i < n; i++) {
                if (nums[i] == nums[i - 1]) {
                    currentStreak++;
                } else {
                    currentStreak = 1;
                }
                maxFreq = Math.max(maxFreq, currentStreak);
            }
        }
        if (numOperations == 0) return maxFreq;

        for (int i = 0; i < n; i++) {
            HashMap<Integer, Integer> counts = new HashMap<>();
            for (int j = i; j < n; j++) {
                if ((long)nums[j] - nums[i] > 2L * k) {
                    break;
                }

                counts.put(nums[j], counts.getOrDefault(nums[j], 0) + 1);
                int m = j - i + 1;

                // Try each element in the window as a target
                for (int p = i; p <= j; p++) {
                    int target = nums[p];
                    // Check if target is valid for the whole window
                    if (Math.max((long)target - nums[i], (long)nums[j] - target) <= k) {
                        int targetCount = counts.get(target);
                        if (m - targetCount <= numOperations && numOperations + targetCount <= n) {
                            maxFreq = Math.max(maxFreq, m);
                        }
                    }
                }
            }
        }
        return maxFreq;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize a variable `maxFreq` to 0, which will store the maximum possible frequency.
3. Iterate through all possible contiguous subarrays of `nums`. This can be done with two nested loops, with outer loop variable `i` from `0` to `N-1` and inner loop variable `j` from `i` to `N-1`.
4. For each subarray `W = nums[i...j]`, check if it's possible to make all its elements equal to a single value.
5. A necessary condition is that `nums[j] - nums[i] <= 2*k`. If this condition is violated, we can break the inner loop and advance `i`, as any further increase in `j` will also violate it.
6. If the condition holds, we need to find if there exists a target value `T` for this subarray. The best candidates for `T` are the elements within the subarray itself, as this maximizes the number of elements that don't need to be changed.
7. We iterate through each unique element `x` in the window `nums[i...j]` and test it as a potential target `T`.
8. For each potential target `x`, we first check if it's valid for the entire window: `max(x - nums[i], nums[j] - x) <= k`.
9. If `x` is a valid target, we calculate its frequency `c` within the window `nums[i...j]`.
10. Let `m = j - i + 1` be the size of the window. The number of operations required is `m - c`. We check if this is feasible with the given constraints: `m - c <= numOperations` and `numOperations + c <= N` (where `N` is the total number of elements).
11. If both constraints are satisfied, it means a frequency of `m` is achievable. We update `maxFreq = max(maxFreq, m)`.
12. After checking all subarrays, `maxFreq` will hold the result.

## Sort and Iterate Through Targets
A more efficient approach is to change the perspective: instead of checking what frequency a subarray can achieve, let's fix a potential target value and calculate the maximum frequency we can achieve for it. The best candidates for a target value are the numbers already present in the array.

This approach iterates through each unique element `x` in the sorted `nums` array, treating it as the target `T`. For each `T=x`, we determine the maximum number of elements we can make equal to `x`. This number is determined by two factors: the number of operations available and the number of elements that are 'close enough' to `x`.

An element `s` is 'close enough' if it can be transformed into `x` by adding a value in `[-k, k]`, which means `s` must be in the range `[x-k, x+k]`. In the sorted array, all such elements form a contiguous block. We can find this block efficiently using binary search.

The number of elements we can make equal to `x` is the sum of its original count (`count_x`) and the number of additional elements we can afford to change (`numOperations`). However, this is capped by the total number of 'close enough' elements we found. We also need to respect a more subtle constraint: the total number of operations must be performable on distinct indices, which leads to the condition `numOperations + count_x <= nums.length`.
**Time:** O(N log N). Sorting takes O(N log N). The main loop iterates through unique elements. For each unique element, it performs two binary searches, taking O(log N). In the worst case, all elements are unique, leading to O(N log N) for the loop. The total complexity is dominated by these two parts. · **Space:** O(1) or O(log N) depending on the sort implementation's space usage. The algorithm itself uses constant extra space.
**Pros:** Highly efficient with O(N log N) time complexity, which passes the given constraints.; The logic is sound and covers all aspects of the problem's constraints once understood.
**Cons:** The logic relies on a subtle understanding of the problem's constraints, particularly how operations are counted and distributed.; Requires careful implementation of binary search (or using library functions) to avoid off-by-one errors.
### Explanation
The algorithm begins by sorting the `nums` array in `O(N log N)` time. This allows for efficient searching and grouping of elements.

The core idea is to iterate through every unique number `x` present in `nums` and calculate the maximum frequency possible if `x` were the target value. For a chosen target `x`, we can form a group of `m` identical values by using its `count_x` original occurrences and converting `m - count_x` other numbers.

The number of operations required is `m - count_x`, which must be less than or equal to `numOperations`. This gives an upper bound on `m`: `m <= count_x + numOperations`.

The elements we convert must be transformable to `x`. An element `s` can be transformed to `x` if `|s - x| <= k`. All such convertible elements lie in the range `[x-k, x+k]`. Since `nums` is sorted, we can find the number of elements in this range in `O(log N)` time using two binary searches (one for the lower bound `x-k` and one for the upper bound `x+k`). Let this count be `numCandidates`.

The size of our final group `m` cannot be larger than `numCandidates`. Thus, we have another upper bound: `m <= numCandidates`.

Combining these, for a target `x`, the maximum frequency is `min(count_x + numOperations, numCandidates)`. We also must satisfy the constraint that we have enough elements outside our target group to perform any leftover operations. This translates to `numOperations + count_x <= N`. If this is violated, we can only achieve a frequency of `count_x`.

We repeat this process for every unique element in `nums` and take the maximum frequency found. The overall time complexity will be `O(N log N)` because of the initial sort and the `O(D log N)` work in the loop, where `D` is the number of distinct elements (`D <= N`).

```java
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        int n = nums.length;
        Arrays.sort(nums);

        int maxFreq = 0;
        if (n > 0) {
            int currentStreak = 0;
            for (int i = 0; i < n; i++) {
                if (i > 0 && nums[i] == nums[i-1]) {
                    currentStreak++;
                } else {
                    currentStreak = 1;
                }
                maxFreq = Math.max(maxFreq, currentStreak);
            }
        }

        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && nums[j] == nums[i]) {
                j++;
            }
            int count = j - i;
            long target = nums[i];

            if (numOperations + count <= n) {
                long minVal = target - k;
                long maxVal = target + k;

                int startIdx = lowerBound(nums, minVal);
                int endIdx = upperBound(nums, maxVal);
                
                int numCandidates = endIdx - startIdx;
                int achievableFreq = Math.min(count + numOperations, numCandidates);
                maxFreq = Math.max(maxFreq, achievableFreq);
            }
            i = j;
        }

        return maxFreq;
    }

    // Finds the first index >= val
    private int lowerBound(int[] arr, long val) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= val) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    // Finds the first index > val
    private int upperBound(int[] arr, long val) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > val) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Pre-calculate the frequency of each unique number in `nums` and store it in a map. This can be done in O(N) on the sorted array.
3. Initialize `maxFreq` to 0. If `numOperations` is 0, the answer is simply the highest frequency of any element, which can be found during pre-calculation.
4. Iterate through each unique element `x` in `nums` (e.g., by iterating through the keys of the frequency map). For each `x`, consider it as the target value `T`.
5. For a target `T=x`, retrieve its original frequency, `count_x`, from the map.
6. Check the constraint `numOperations + count_x <= N`. If this fails, it means we are forced to operate on elements we want to keep as `x`. In this case, the maximum frequency we can achieve for `x` is just `count_x`. Update `maxFreq = max(maxFreq, count_x)` and proceed to the next unique element.
7. If the constraint holds, find all elements in `nums` that can be converted to `x`. These are elements `s` where `|x - s| <= k`, which means `s` must be in the range `[x - k, x + k]`.
8. In the sorted `nums` array, these candidate elements form a contiguous block. Use binary search (`lower_bound` and `upper_bound`) to find the start index `l` and end index `r` of this block.
9. The total number of candidates available to form the target `x` is `numCandidates = r - l + 1`.
10. With `numOperations`, we can change up to `numOperations` other elements into `x`. So, the potential frequency is `count_x + numOperations`.
11. This potential frequency is limited by the number of available candidates. Therefore, the maximum frequency achievable with `x` as the target is `achievableFreq = min(count_x + numOperations, numCandidates)`.
12. Update `maxFreq = max(maxFreq, achievableFreq)`.
13. After checking all unique elements as potential targets, `maxFreq` will hold the final answer.

# Solutions
### Java

```java
class Solution {
public
  int maxFrequency(int[] nums, int k, int numOperations) {
    Map<Integer, Integer> cnt = new HashMap<>();
    TreeMap<Integer, Integer> d = new TreeMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer : : sum);
      d.putIfAbsent(x, 0);
      d.merge(x - k, 1, Integer : : sum);
      d.merge(x + k + 1, -1, Integer : : sum);
    }
    int ans = 0, s = 0;
    for (var e : d.entrySet()) {
      int x = e.getKey(), t = e.getValue();
      s += t;
      ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxFrequency(vector<int> &nums, int k, int numOperations) {
    unordered_map<int, int> cnt;
    map<int, int> d;
    for (int x : nums) {
      cnt[x]++;
      d[x];
      d[x - k]++;
      d[x + k + 1]--;
    }
    int ans = 0, s = 0;
    for (const auto &[x, t] : d) {
      s += t;
      ans = max(ans, min(s, cnt[x] + numOperations));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int: cnt = defaultdict(int) d = defaultdict(int) for x in nums: cnt[x] += 1 d[x] += 0 d[x - k] += 1 d[x + k + 1] -= 1 ans = s = 0 for x, t in sorted(d . items()): s += t ans = max(ans, min(s, cnt[x] + numOperations)) return ans

```