> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/sliding-window/1838.-frequency-of-the-most-frequent-element.md).

# 1838. Frequency of the Most Frequent Element

## Problem Statement

<br>

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*.

&#x20;

**Example 1:**

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

**Example 2:**

<pre><code><strong>Input: nums = [1,4,8,13], k = 5
</strong><strong>Output: 2
</strong><strong>Explanation: There are multiple optimal solutions:
</strong>- 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.
</code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [3,9,6], k = 2
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Bascially,
We have to find maximum frequency, So if we consider for an array of size 4
So we need to find if we can convert all other to maximum elements in that

So max freq can be N and min 1
1-N we can binary search the window and mid will represent the Sliding window

So if we can acheive the window in k operations

1 4 8 13
Let say window of size 3 
1 4 8 find if can all other can be converted to 8 in k oprations
total operations 8*3 - 1 +4 + 8 find prefix sum for window size

then we can reuse for 4 8 13 shifting window
```

### Links

<https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/>

### Video Links

<https://www.youtube.com/watch?v=nveGJc_oYAI&ab_channel=AdityaRajiv>\
\
<https://www.youtube.com/watch?v=vgBrQ0NM5vE&ab_channel=NeetCode>

### Approach 1:

```
BS + Prefix sum + Sliding window
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool possible(vector<int>& nums, int mid, int k){
        long long int window=0;

        for(int i=0; i<mid; i++)
            window += nums[i];

        long long int total = nums[mid-1] * (long long int)mid;

        if(total - window <= k)
            return true;

        int j=0;
        for(int i=mid; i<nums.size(); i++){
            window -= nums[j++];
            window += nums[i];

            long long int total = nums[i] * (long long int)mid;

            if(total - window <= k)
                return true;
        }

        return false;
    }

    int maxFrequency(vector<int>& nums, int k) {
        int low=1, high=nums.size();
        int ans;
        sort(nums.begin(), nums.end());

        while(low<=high){
            int mid = low + (high-low)/2;

            if(possible(nums, mid, k)){
                ans = mid;
                low = mid+1;
            }

            else
                high = mid-1;
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
Sliding window

Basically in each interval we track if we can convert all the elemets
to last element like this

1 1 1 2 2 4   k=2
  L     R

Here in this interval We try to convert all to Rth element

So (2*4 (Size of interval)) <= Window_sum + K(operations)
Lets check

If that window is changes to 2
2*4 = 8 <= 6+2(opearations = no of values or sum increased)
Allowed here, take that window

```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 0, window = 1;
        long long sum = 0;
        int ans = 0;
        sort(nums.begin(), nums.end());
        
        for(int high = 0; high<n; high++){
            sum += nums[high];
            window = high-low+1;

            while((long long)nums[high]*window > sum+k){
                sum -= nums[low++];
                window = high-low+1;
            }
            
            ans = max(window, ans);
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###