- Difficulty: Medium.

- Related Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum.

- Similar Questions: Find All Lonely Numbers in the Array, Longest Nice Subarray.

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:

Example 2:

Example 3:

 

**Constraints:**

- ```1 <= nums.length <= 105```

- ```1 <= nums[i] <= 105```

- ```1 <= k <= 105```

var maxFrequency = function(nums, k) {

nums.sort((a, b) => a - b);

var sums = Array(nums.length);

nums.forEach((num, i) => sums[i] = (sums[i - 1] || 0) + num);

var max = 0;

for (var i = 0; i < nums.length; i++) {

var frequency = i + 1 - binarySearch(nums, sums, i, k);

max = Math.max(max, frequency);

}

return max;

};

var binarySearch = function(nums, sums, i, k) {

var left = 0;

var right = i;

var getValue = (j) => {

return nums[i] * (i - j + 1) - (sums[i] - sums[j] + nums[j]);

};

while (left <= right) {

var mid = left + Math.floor((right - left) / 2);

var midValue = getValue(mid);

if (midValue === k) {

return mid;

} else if (midValue > k) {

left = mid + 1;

} else {

if (mid === left) return mid;

right = mid;

}

}

return i;

};

**Explain:**

1. sort the array of nums by ascending order

2. calculate prefix sum array

3. for every nums[i], binary search possible index in [0, i],

which can use k operates, to make every num in [index, i] equals nums[i]

**Complexity:**

* Time complexity : O(nlog(n)).

* Space complexity : O(n).