# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/sliding-window/1838.-frequency-of-the-most-frequent-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.