1838. Frequency of the Most Frequent Element

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

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
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).