# Maximum Frequency of an Element After Performing Operations I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-frequency-of-an-element-after-performing-operations-i
**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]`. `nums` becomes `[1, 4, 5]`.
* Adding -1 to `nums[2]`. `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] <= 105`
* `0 <= k <= 105`
* `0 <= numOperations <= nums.length`

# Approaches
## Brute-Force with Candidate Targets
This approach is based on the idea of testing a set of potential 'target' values that the elements of `nums` could be converted to. For any given target value `T`, we can calculate the maximum frequency we can achieve for it. The final answer will be the maximum frequency found across all possible target values.

The core of this method is to determine which values of `T` are worth checking. The number of elements that can be transformed into `T` depends on the range `[T-k, T+k]`. The count of elements within this range only changes when the boundaries `T-k` or `T+k` cross an element `nums[i]`, or when `T` itself crosses an element `nums[i]`. This implies that the optimal `T` must be one of `nums[i]`, `nums[i]-k`, or `nums[i]+k` for some `i`. Therefore, we can limit our search to this set of candidate values.

For each candidate target, we iterate through the entire `nums` array to count how many elements are already equal to the target (`exactMatches`) and how many can be changed to the target (`possibleMatches`). With `numOperations` available, we can convert `min(numOperations, possibleMatches)` elements. The total frequency for that target is the sum of `exactMatches` and the number of converted elements.
**Time:** O(N^2), where N is the number of elements in `nums`. The number of candidate targets can be up to O(N). For each candidate, we iterate through the entire `nums` array, which takes O(N) time. This results in a total time complexity of O(N) * O(N) = O(N^2). · **Space:** O(N), where N is the number of elements in `nums`. This is for storing the candidate target values in a set. In the worst case, there can be up to 3N distinct candidates.
**Pros:** Simple to understand and implement.; Correctly identifies the necessary set of candidate target values to check.
**Cons:** The time complexity of O(N*C) where C is the number of candidates (up to 3N) makes it too slow for the given constraints (N up to 10^5), leading to a Time Limit Exceeded error.
### Explanation
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Set<Long> candidates = new HashSet<>();
        for (int num : nums) {
            candidates.add((long) num);
            candidates.add((long) num - k);
            candidates.add((long) num + k);
        }

        int maxFreq = 0;
        for (long target : candidates) {
            int exactMatches = 0;
            int possibleMatches = 0;
            for (int num : nums) {
                if (num == target) {
                    exactMatches++;
                } else if (Math.abs(num - target) <= k) {
                    possibleMatches++;
                }
            }
            int currentFreq = exactMatches + Math.min(numOperations, possibleMatches);
            maxFreq = Math.max(maxFreq, currentFreq);
        }
        return maxFreq;
    }
}
```
### Algorithm
1.  Identify a set of candidate target values. A crucial observation is that an optimal target value `T` must be 'close' to the numbers in the input array. A comprehensive set of candidates includes `nums[i]`, `nums[i] - k`, and `nums[i] + k` for every element `nums[i]` in the array. This is because the function we are trying to maximize changes its value only at these points.
2.  Store these candidate values in a `Set` to handle duplicates.
3.  Initialize a variable `maxFreq` to 0.
4.  Iterate through each `target` in the set of candidates:
    a.  For the current `target`, calculate the number of elements that can be made equal to it. We need two counts:
        i.  `exactMatches`: The number of elements in `nums` that are already equal to `target`.
        ii. `possibleMatches`: The number of elements `num` in `nums` such that `num != target` but `|num - target| <= k`. These elements can be converted to `target` using one operation.
    b.  The total frequency for the current `target` is `exactMatches + min(numOperations, possibleMatches)`. We can use up to `numOperations` to convert the `possibleMatches`.
    c.  Update `maxFreq = max(maxFreq, currentFreq)`.
5.  After checking all candidates, `maxFreq` will hold the result.

## Sorting with Binary Search
The brute-force approach is slow because for each candidate target, we scan the entire array. We can optimize this calculation by first sorting the `nums` array. Once the array is sorted, counting elements within a specific range `[minVal, maxVal]` can be done much faster than a linear scan.

By using binary search, we can find the number of elements in the range `[target - k, target + k]` in `O(log N)` time. We can implement helper functions like `lower_bound` and `upper_bound` to find the start and end of this range in the sorted array. The rest of the logic remains the same: generate candidate targets, and for each, calculate the achievable frequency. The frequency of each number can also be pre-computed and stored in a hash map to speed up lookups for `exactMatches`.
**Time:** O(N log N). Sorting takes O(N log N). Generating candidates takes O(N). The main loop runs O(N) times, and each iteration takes O(log N) for binary search. So, the total time is dominated by O(N log N). · **Space:** O(N) for storing candidates, the frequency map, and the sorted copy of the array (if not sorted in-place).
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass the time limits for the given constraints.
**Cons:** The number of candidates can still be large (O(N)), so the loop runs many times.; While better than O(N^2), it might not be the most optimal solution possible.
### Explanation
```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        Set<Long> candidates = new HashSet<>();
        for (int num : nums) {
            candidates.add((long) num);
            candidates.add((long) num - k);
            candidates.add((long) num + k);
        }

        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int maxFreq = 0;
        for (long target : candidates) {
            int exactMatches = freqMap.getOrDefault((int) target, 0);

            long low = target - k;
            long high = target + k;

            int startIdx = lower_bound(nums, low);
            int endIdx = upper_bound(nums, high);

            int rangeCount = endIdx - startIdx;
            int possibleMatches = rangeCount - exactMatches;

            int currentFreq = exactMatches + Math.min(numOperations, possibleMatches);
            maxFreq = Math.max(maxFreq, currentFreq);
        }
        return maxFreq;
    }

    private int lower_bound(int[] nums, long val) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= val) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private int upper_bound(int[] nums, long val) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > val) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }        
        return l;
    }
}
```
### Algorithm
1.  First, sort the input array `nums`.
2.  Generate the same set of candidate targets as in the brute-force approach: `nums[i]`, `nums[i]-k`, and `nums[i]+k` for all `i`.
3.  Pre-calculate the frequency of each number in `nums` and store it in a hash map for O(1) lookup.
4.  Iterate through each `target` in the candidate set:
    a.  Get `exactMatches` for the `target` from the frequency map.
    b.  The key optimization is to find the count of numbers in the range `[target - k, target + k]` efficiently. Since `nums` is sorted, we can do this in `O(log N)` time using binary search. We find the index of the first element greater than `target + k` (`upper_bound`) and the index of the first element greater than or equal to `target - k` (`lower_bound`). The difference between these indices gives the `rangeCount`.
    c.  `possibleMatches = rangeCount - exactMatches`.
    d.  `currentFreq = exactMatches + min(numOperations, possibleMatches)`.
    e.  Update the overall `maxFreq`.
5.  Return `maxFreq`.

## Optimized Sweep-line and Two-Pointers
This approach provides a more fine-grained analysis to optimize the calculation. We split the problem into two cases based on the optimal target value `T`.

**Case 1: The optimal target `T` is one of the numbers present in the input array `nums`.**
We can iterate through each unique value `v` in `nums` and calculate the maximum frequency achievable with `v` as the target. After sorting `nums`, we can find the count of elements in `[v-k, v+k]` for all unique `v` efficiently using a two-pointer approach in `O(N)` time, which is better than repeated binary searches.

**Case 2: The optimal target `T` is not a number present in `nums`.**
In this case, the number of exact matches `C(T)` is 0. The formula for frequency becomes `min(R(T), numOperations)`. To maximize this, we need to find the maximum possible value of `R(T)`, which is the maximum number of elements that can fall into any window of size `2k`. This is a classic maximum interval overlap problem, solvable with a sweep-line algorithm. By creating start and end events for each interval `[num-k, num+k]`, we can find the point of maximum overlap.

The final answer is the maximum of the frequencies found in these two cases. The overall time complexity is dominated by the initial sort of `nums`.
**Time:** O(N log N). Sorting `nums` takes O(N log N). Part A (two-pointers) takes O(N). Part B (sweep-line with TreeMap) takes O(N log N) due to map insertions. If implemented with sorted arrays and merging for the sweep-line, it would be O(N). The bottleneck remains the initial sort. · **Space:** O(N) for storing unique numbers, frequencies, and sweep-line events.
**Pros:** Most efficient approach with O(N log N) complexity.; Breaks down the problem into logical subproblems that can be solved optimally.; The linear-time components (two-pointers, sweep-line after sort) make it fast in practice.
**Cons:** More complex to understand and implement correctly compared to the previous approaches.
### Explanation
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

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

        // Part 1: Calculate max frequency for targets T that are present in nums
        Map<Integer, Integer> freqMap = new HashMap<>();
        List<Integer> uniqueNums = new ArrayList<>();
        uniqueNums.add(nums[0]);
        freqMap.put(nums[0], 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1]) {
                uniqueNums.add(nums[i]);
            }
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }

        int maxFreqAtNum = 0;
        int l = 0, r = 0;
        for (int target : uniqueNums) {
            long minVal = (long) target - k;
            long maxVal = (long) target + k;
            while (l < n && nums[l] < minVal) {
                l++;
            }
            while (r < n && nums[r] <= maxVal) {
                r++;
            }
            int rangeCount = r - l;
            int exactMatches = freqMap.get(target);
            int possibleMatches = rangeCount - exactMatches;
            maxFreqAtNum = Math.max(maxFreqAtNum, exactMatches + Math.min(numOperations, possibleMatches));
        }

        // Part 2: Calculate max frequency for targets T not in nums
        // This is min(max_T R(T), numOperations)
        Map<Long, Integer> sweep = new TreeMap<>();
        for (int num : nums) {
            long start = (long) num - k;
            long end = (long) num + k;
            sweep.put(start, sweep.getOrDefault(start, 0) + 1);
            sweep.put(end + 1, sweep.getOrDefault(end + 1, 0) - 1);
        }

        int maxRangeCount = 0;
        int currentRangeCount = 0;
        for (int count : sweep.values()) {
            currentRangeCount += count;
            maxRangeCount = Math.max(maxRangeCount, currentRangeCount);
        }
        
        int maxFreqBetweenNums = Math.min(maxRangeCount, numOperations);

        return Math.max(maxFreqAtNum, maxFreqBetweenNums);
    }
}
```
### Algorithm
1.  The achievable frequency for a target `T` is `f(T) = min(R(T), C(T) + numOperations)`, where `R(T)` is the count of `nums` in `[T-k, T+k]` and `C(T)` is the count of `nums` equal to `T`.
2.  The maximum of `f(T)` occurs either when `T` is one of the values in `nums`, or at a point where `R(T)` is maximized (in which case `C(T)=0`).
3.  Sort `nums`. This takes `O(N log N)`.
4.  **Part A: Calculate max frequency for targets `T` in `nums`.**
    a.  Get unique sorted values from `nums` and their frequencies (`C(T)`).
    b.  For each unique `T`, calculate `R(T)`. Instead of repeated binary searches, use a two-pointer/sliding window approach on the sorted `nums` array. As `T` iterates through unique values, the window `[T-k, T+k]` slides. This allows calculating all `R(T)` values in `O(N)` total time.
    c.  Compute `f(T)` for each unique `T` and find the maximum, let's call it `maxFreqAtNum`.
5.  **Part B: Calculate max frequency for targets `T` not in `nums`.**
    a.  This simplifies to `min(max_T R(T), numOperations)`.
    b.  `max_T R(T)` is the problem of finding the maximum overlap among intervals `[num-k, num+k]` for all `num` in `nums`.
    c.  This can be solved with a sweep-line algorithm. Create event points `(num-k, +1)` and `(num+k+1, -1)`. Sort these events and sweep through them, keeping track of the active interval count. The maximum count is `max_T R(T)`.
    d.  Since `nums` is sorted, the start points `num-k` and end points `num+k+1` are also sorted. We can merge them in `O(N)` time to find the max overlap without a full sort of events.
6.  The final answer is the maximum of the results from Part A and Part B.

# 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

```