Frequency of the Most Frequent Element — Medium Problem & Solution

In one operation you may increment any element of nums by 1. You may perform at most k operations in total.

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, Binary Search, Sliding Window
Asked at: Amazon, Google, Salesforce
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In one operation you may increment any element of nums by 1. You may perform at most k operations in total.

Return the maximum possible frequency of any single value afterwards.

Example 1

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Raise 1 to 4 (3 operations) and 2 to 4 (2 more) — every element becomes 4.

Example 2

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: Raising 4 to 8 costs 4.

Example 3

Input: nums = [3,9,6], k = 2
Output: 1

Constraints

1 <= nums.length <= 100000
1 <= nums[i] <= 100000
1 <= k <= 100000000

How to solve Frequency of the Most Frequent Element

Sorting makes the cheapest group of equal values contiguous, because raising an element to a target costs the gap and you would never skip a nearer element for a further one. The cost of a window is then a closed form, and it is monotone in the window's width.

Approach

Sort nums.
Slide a window; on adding a[r], the cost to level the window to a[r] is a[r] · (r - l + 1) - windowSum.
While that exceeds k, drop a[l] and advance l.
Track the widest valid window.

Why it works

With increments only, the target must be the window's maximum, which after sorting is a[r]. Widening the window on the left adds a smaller element, so the levelling cost only ever increases — the predicate is monotone and a single left pointer suffices. Each index enters and leaves once.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

a[r] · windowSize reaches 10^5 · 10^5 = 10^10 — the arithmetic needs 64-bit even though the answer is small.
Targeting a value not present in the array is never better, since lowering the target can only reduce the cost.
The answer is at least 1, so seed the best accordingly.

Reference solution

Python

from typing import List

def maxFrequency(nums: List[int], k: int) -> int:
    a = sorted(nums)
    l = 0
    total = 0
    best = 1
    for r in range(len(a)):
        total += a[r]
        while a[r] * (r - l + 1) - total > k:
            total -= a[l]
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var maxFrequency = function(nums, k) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var l = 0, sum = 0, best = 1;
    for (var r = 0; r < a.length; r++) {
        sum += a[r];
        while (a[r] * (r - l + 1) - sum > k) { sum -= a[l]; l++; }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue