Frequency of the Most Frequent Element

Problem#

In one operation increment any element by 1. With at most k operations, return the maximum possible frequency of any element.

Examples#

nums = [1,2,4], k = 5 → 3 (raise 1 to 4 with 3 ops, 2 to 4 with 2 ops)
nums = [1,4,8,13], k = 5 → 2

Constraints#

1 <= nums.length <= 10^5, 1 <= k <= 10^5.

Hints#

Hint 1

Sort first. The most-frequent value will be the right end of some sorted window; cost = (r - l + 1) * nums[r] - prefixSum.

Approach#

Sort. Slide a window [l, r]; the right end is the target value. Cost to raise everything in the window to nums[r] is nums[r]*(r - l + 1) - sum(window). Shrink while cost > k.

Solution#

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long sum = 0;
        int left = 0, best = 1;
        for (int right = 0; right < (int)nums.size(); ++right) {
            sum += nums[right];
            while ((long long)nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

import "sort"

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    var sum int64 = 0
    left, best := 0, 1
    for right := 0; right < len(nums); right++ {
        sum += int64(nums[right])
        for int64(nums[right])*int64(right-left+1)-sum > int64(k) {
            sum -= int64(nums[left])
            left++
        }
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

from typing import List

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        s = 0
        left = 0
        best = 1
        for right in range(len(nums)):
            s += nums[right]
            while nums[right] * (right - left + 1) - s > k:
                s -= nums[left]
                left += 1
            best = max(best, right - left + 1)
        return best

var maxFrequency = function(nums, k) {
    nums.sort((a, b) => a - b);
    let sum = 0;
    let left = 0, best = 1;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (nums[right] * (right - left + 1) - sum > k) {
            sum -= nums[left++];
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
};

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        long sum = 0;
        int left = 0, best = 1;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while ((long) nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

function maxFrequency(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let sum = 0;
    let left = 0, best = 1;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (nums[right] * (right - left + 1) - sum > k) {
            sum -= nums[left++];
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Editorial#

Sorting unlocks the window: the cheapest way to make a group equal to v is to start from values ≤ v sorted by closeness. The cost formula target * count - sum is the prefix-sum identity. Cast to long long early — nums[right] * (right - left + 1) can overflow for the max constraints.

Complexity#

Time: O(n log n).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#