Frequency of the Most Frequent Element

Medium
791.

Frequency of the Most Frequent Element

Frequency of the Most Frequent Element is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Salesforce interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxFrequency = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Frequency of the Most Frequent Element — Problem & Solution

Frequency of the Most Frequent Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Frequency of the Most Frequent Element is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Salesforce interviews.

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

Hints for Frequency of the Most Frequent Element

  1. Hint 1

    Only increments are allowed, so the final common value must be one of the existing elements — the largest in the group.

  2. Hint 2

    Sort, then ask: for a window ending at r, what does it cost to raise everything in it to nums[r]?

  3. Hint 3

    That cost is nums[r] · windowSize − windowSum, which grows as the window widens.

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

  1. Sort nums.
  2. Slide a window; on adding a[r], the cost to level the window to a[r] is a[r] · (r - l + 1) - windowSum.
  3. While that exceeds k, drop a[l] and advance l.
  4. 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

Java

public static int maxFrequency(int[] nums, int k) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int l = 0, best = 1;
    long sum = 0;
    for (int r = 0; r < a.length; r++) {
        sum += a[r];
        while ((long) a[r] * (r - l + 1) - sum > k) {
            sum -= a[l];
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int maxFrequency(vector<int>& nums, int k) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int l = 0, best = 1;
    long long sum = 0;
    for (int r = 0; r < (int) a.size(); r++) {
        sum += a[r];
        while ((long long) a[r] * (r - l + 1) - sum > k) {
            sum -= a[l];
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms