# Frequency of the Most Frequent Element
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/frequency-of-the-most-frequent-element)
Canonical: https://scaleengineer.com/dsa/problems/frequency-of-the-most-frequent-element
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [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), [Pony.ai](https://scaleengineer.com/companies/pony.ai), [CRED](https://scaleengineer.com/companies/cred)
---
## Problem
The **frequency** of an element is the number of times it occurs in an array.

You are given an integer array `nums` and an integer `k`. In one operation, you can choose an index of `nums` and increment the element at that index by `1`.

Return _the **maximum possible frequency** of an element after performing **at most**_ `k` _operations_.

**Example 1:**

**Input:** nums = [1,2,4], k = 5
**Output:** 3
**Explanation:** Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

**Example 2:**

**Input:** nums = [1,4,8,13], k = 5
**Output:** 2
**Explanation:** There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

**Example 3:**

**Input:** nums = [3,9,6], k = 2
**Output:** 1

**Constraints:**

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

# Approaches
## Brute Force with Prefix Sum
This approach involves checking every possible contiguous subarray after sorting the input array. The core idea is that to maximize frequency, we should pick a group of numbers and make them all equal to the largest number in that group. Sorting helps because any such optimal group will form a contiguous subarray in the sorted array. We use a prefix sum array to quickly calculate the sum of elements in any subarray, which optimizes the calculation from O(N) to O(1) for each subarray, but the overall complexity remains quadratic.
**Time:** O(N^2). Sorting takes O(N log N). The nested loops to check all relevant subarrays take O(N^2) time. The overall complexity is dominated by the nested loops. · **Space:** O(N) for storing the prefix sum array. The space for sorting can also be up to O(N) depending on the implementation.
**Pros:** Conceptually simpler than more optimized approaches.; It correctly identifies the subproblem structure after sorting.
**Cons:** This approach is too slow for the given constraints (`N <= 10^5`) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
First, we sort the input array `nums`. This is a key step because if we want to make a set of elements equal, it's always optimal to make them equal to the largest element in that set. After sorting, any such optimal set of elements will form a contiguous subarray.

To avoid re-calculating the sum of each subarray in the inner loop, we can pre-compute a prefix sum array. The prefix sum `prefix[i]` will store the sum of all elements from `nums[0]` to `nums[i-1]`. With this, the sum of any subarray `nums[i...j]` can be found in O(1) time by `prefix[j+1] - prefix[i]`.

We then iterate through all possible subarrays using two nested loops. The outer loop with index `j` determines the right end of the subarray, making `nums[j]` the target value. The inner loop with index `i` determines the left end. For each subarray `nums[i...j]`, we calculate the cost to make all its elements equal to `nums[j]`. The cost is the difference between the total value of the desired array (all elements are `nums[j]`) and the current sum of the subarray. This is `(j - i + 1) * nums[j] - sum(nums[i...j])`.

If the calculated cost is within our budget `k`, we have found a valid frequency of `j - i + 1`, and we update our overall maximum frequency. If the cost exceeds `k`, we can stop checking smaller `i` for the current `j` because making the subarray longer will only increase the cost.

```java
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int maxFreq = 0;
        // Any single element has a frequency of at least 1
        if (n > 0) maxFreq = 1;

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                long windowSize = j - i + 1;
                long windowSum = prefixSum[j + 1] - prefixSum[i];
                long cost = windowSize * nums[j] - windowSum;
                if (cost <= k) {
                    maxFreq = Math.max(maxFreq, (int)windowSize);
                } else {
                    // Since the array is sorted, any window starting before i
                    // will also have a cost > k for the same endpoint j.
                    break; 
                }
            }
        }
        return maxFreq;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- To efficiently calculate the sum of elements in any subarray, precompute a prefix sum array. The prefix sum `prefix[i]` stores the sum of all elements from `nums[0]` to `nums[i-1]`.
- Use a nested loop. The outer loop (`j`) fixes the right endpoint of the subarray (and thus the target value `nums[j]`), and the inner loop (`i`) iterates from `j` down to `0` to define the left endpoint.
- For each subarray `nums[i...j]`, calculate the number of operations needed to make all its elements equal to `nums[j]`. The cost is `(window_size * target_value) - window_sum`, which translates to `(long)(j - i + 1) * nums[j] - (prefix[j+1] - prefix[i])`.
- If this cost is less than or equal to `k`, it means we can form a group of size `j - i + 1`. We update our maximum frequency found so far.
- If the cost exceeds `k`, we can break the inner loop for the current `j`, as extending the subarray to the left will only increase the cost.

## Binary Search on the Answer
A more efficient approach uses binary search on the possible answer, which is the frequency. The key observation is that if we can achieve a frequency of `x` with at most `k` operations, we can also achieve any frequency less than `x`. This monotonic property (if a frequency `x` is possible, all frequencies `< x` are also possible) allows us to binary search for the maximum possible frequency.
**Time:** O(N log N). Sorting takes O(N log N). The binary search performs log N iterations, and each `isPossible` check takes O(N) time. Thus, the search part is O(N log N). The total complexity is O(N log N). · **Space:** O(N) for the prefix sum array. The space for sorting can be O(log N) to O(N).
**Pros:** Significantly faster than the brute-force approach.; Efficient enough to pass the given constraints.; A good example of the 'binary search on the answer' pattern.
**Cons:** Requires extra O(N) space for the prefix sum array.; The logic is more complex than brute force, involving a helper function and understanding the monotonic property.
### Explanation
The range of possible answers for the maximum frequency is from 1 to N. We can apply binary search on this answer space.

For a given frequency `len` that we want to test, we need an efficient way to check if it's possible to make `len` elements equal using at most `k` operations. This check is done in a helper function, `isPossible(len)`.

First, we sort the `nums` array and precompute prefix sums. This setup allows the `isPossible` check to be performed efficiently. The `isPossible(len)` function iterates through all contiguous subarrays (windows) of size `len` in the sorted array. For each window, it calculates the cost to make all its elements equal to the largest element in that window (the rightmost one). The cost for a window `nums[i...i+len-1]` is `len * nums[i+len-1] - sum(nums[i...i+len-1])`. Using the prefix sum array, this sum is found in O(1). If this cost is `<= k` for any window, it means a frequency of `len` is achievable, and `isPossible(len)` returns `true`.

In the main binary search loop, if `isPossible(mid)` is true, we know `mid` is a valid frequency, so we record it and search for an even larger frequency in the right half of our search space (`low = mid + 1`). If it's false, `mid` is too high, and we must search for a smaller frequency in the left half (`high = mid - 1`).

```java
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        int low = 1, high = n;
        int ans = 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(mid, nums, k, prefixSum)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int len, int[] nums, int k, long[] prefixSum) {
        int n = nums.length;
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            long windowSum = prefixSum[j + 1] - prefixSum[i];
            long cost = (long)len * nums[j] - windowSum;
            if (cost <= k) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Sort the `nums` array.
- Create a prefix sum array `prefix` for O(1) window sum calculation.
- Initialize a search range for the answer: `low = 1`, `high = n`, and `ans = 1`.
- Perform a binary search on this range:
  - Calculate `mid = low + (high - low) / 2`. `mid` is the frequency we are checking.
  - Call a helper function `isPossible(mid)` to check if a frequency of `mid` is achievable within `k` operations.
  - If `isPossible(mid)` is true, it means a frequency of `mid` is possible. We store `mid` as a potential answer and try for a larger frequency by setting `low = mid + 1`.
  - If `isPossible(mid)` is false, `mid` is too large, so we search in the lower half by setting `high = mid - 1`.
- Return the final `ans`.

**`isPossible(len)` function:**
- Iterate through all windows of size `len` in the sorted `nums` array (from `i = 0` to `n - len`).
- For each window `nums[i...i+len-1]`, calculate the cost to make all elements equal to `nums[i+len-1]`.
- The cost is `(long)len * nums[i+len-1] - (prefix[i+len] - prefix[i])`.
- If `cost <= k` for any window, return `true` immediately.
- If the loop finishes without finding such a window, return `false`.

## Sliding Window
The most optimal solution uses the sliding window technique. After sorting the array, the problem transforms into finding the longest subarray `nums[i...j]` where all elements can be made equal to `nums[j]` with at most `k` operations. This 'longest subarray satisfying a condition' structure is a classic indicator for a sliding window approach, which provides a linear-time scan after the initial sort.
**Time:** O(N log N). Sorting takes O(N log N). The sliding window part takes O(N) because both `left` and `right` pointers traverse the array at most once. The overall complexity is dominated by sorting. · **Space:** O(log N) or O(N) depending on the space used by the sorting algorithm. Ignoring the sort, the space complexity is O(1).
**Pros:** Most efficient approach. The logic after sorting is O(N), which is faster than the O(N log N) post-sort work of the binary search approach.; Uses constant extra space (O(1)), aside from the space required for sorting.
**Cons:** The initial sorting step still makes the overall time complexity O(N log N), not linear.; Can be slightly less intuitive to devise compared to binary search if one is not familiar with the sliding window pattern.
### Explanation
This approach is based on the sliding window technique, which is highly efficient for problems involving contiguous subarrays. As with other approaches, the first step is to sort `nums`.

We use two pointers, `left` and `right`, to define the current window. The `right` pointer expands the window, and the `left` pointer shrinks it. We also maintain `currentSum`, the sum of elements within the window `nums[left...right]`.

We iterate with the `right` pointer from the beginning to the end of the array. In each step, we add `nums[right]` to `currentSum`. Now, we have a new, larger window. We must check if this window is 'valid'. A window is valid if we can make all its elements equal to `nums[right]` (the largest element) using at most `k` operations. The cost for this is `(window_size * nums[right]) - currentSum`.

If this cost exceeds `k`, the window is invalid. We need to shrink it by moving the `left` pointer to the right. We subtract `nums[left]` from `currentSum` and increment `left`. We repeat this process until the window's cost is no longer greater than `k`.

After ensuring the window is valid, its size (`right - left + 1`) is a candidate for the maximum frequency. We update our answer, `maxFreq`, with the maximum size seen so far. Since the `right` pointer only moves forward, and the `left` pointer never moves backward, each element is processed a constant number of times, leading to a linear time complexity for the window traversal.

```java
import java.util.Arrays;

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

        for (int right = 0; right < n; right++) {
            currentSum += nums[right];
            
            // Condition to check if the current window is valid.
            // We need (window size) * nums[right] - currentSum <= k
            while ((long)(right - left + 1) * nums[right] - currentSum > k) {
                currentSum -= nums[left];
                left++;
            }
            
            maxFreq = Math.max(maxFreq, right - left + 1);
        }
        
        return maxFreq;
    }
}
```
### Algorithm
- Sort the array `nums`.
- Initialize a left pointer `left = 0`, a variable for the result `maxFreq = 0`, and a running sum `currentSum = 0`.
- Iterate through the array with a right pointer `right` from `0` to `n-1`:
  - Add `nums[right]` to `currentSum` to expand the window.
  - Check if the current window `nums[left...right]` is valid. The condition is `(window_size * target_value) - window_sum <= k`. This translates to `(long)(right - left + 1) * nums[right] - currentSum <= k`.
  - If the condition is violated (cost > k), shrink the window from the left: subtract `nums[left]` from `currentSum` and increment `left`. Repeat this in a `while` loop until the window becomes valid again.
  - After the `while` loop, the window `nums[left...right]` is the largest valid window ending at `right`. Update `maxFreq = max(maxFreq, right - left + 1)`.
- After the loop finishes, return `maxFreq`.

# Solutions
### Java

```java
class Solution {
public
  int maxFrequency(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length;
    int ans = 1, window = 0;
    for (int l = 0, r = 1; r < n; ++r) {
      window += (nums[r] - nums[r - 1]) * (r - l);
      while (window > k) {
        window -= (nums[r] - nums[l++]);
      }
      ans = Math.max(ans, r - l + 1);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ var maxFrequency =
  function (nums, k) {
    nums.sort((a, b) => a - b);
    let ans = 1;
    let window = 0;
    const n = nums.length;
    for (let l = 0, r = 1; r < n; ++r) {
      window += (nums[r] - nums[r - 1]) * (r - l);
      while (window > k) {
        window -= nums[r] - nums[l++];
      }
      ans = Math.max(ans, r - l + 1);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int maxFrequency(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int ans = 1;
    long long window = 0;
    for (int l = 0, r = 1; r < n; ++r) {
      window += 1LL * (nums[r] - nums[r - 1]) * (r - l);
      while (window > k) {
        window -= (nums[r] - nums[l++]);
      }
      ans = max(ans, r - l + 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int: nums . sort() l, r, n = 0, 1, len(nums) ans, window = 1, 0 while r < n: window += (nums[r] - nums[r - 1]) * (r - l) while window > k: window -= nums[r] - nums[l] l += 1 r += 1 ans = max(ans, r - l) return ans

```