Frequency of the Most Frequent Element

Master this topic with zero to advance depth.

Frequency of the Most Frequent Element

Maximize the frequency of an element by incrementing other elements by at most k overall.

Visual Representation

nums = [1, 2, 4], k = 5

Sort: [1, 2, 4]
Window [1, 2, 4] ending at 4:
Cost to make all 4: (4-1) + (4-2) + (4-4) = 3 + 2 + 0 = 5
Cost 5 <= k (5)? YES! Frequency = 3

Medium

Examples

Input: nums = [1,2,4], k = 5
Output: 3

Approach 1

Level I: Brute Force

Intuition

For each element x in the array, try to make a sequence of elements equal to x ending at x. Use a sliding window to find the maximum possible frequency for each starting position.

Thought Process

Sort the array.
Iterate i from 0 to n-1.
Iterate j from i to n-1.
Calculate cost = sum(nums[j] - nums[k]) for k in [i...j].
If cost <= k, maxFreq = max(maxFreq, j - i + 1).

⏱ O(N^2)💾 O(1)

Detailed Dry Run

j	Window	Cost	Max Freq
0	[1]	0	1
1	[1, 2]	(2-1) = 1	2
2	[1, 2, 4]	(4-1)+(4-2) = 5	3

java

import java.util.*;
public class Main {
    public static int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, maxFreq = 1;
        for (int i = 0; i < n; i++) {
            long cost = 0;
            for (int j = i + 1; j < n; j++) {
                cost += (long)(j - i) * (nums[j] - nums[j-1]);
                if (cost <= k) maxFreq = Math.max(maxFreq, j - i + 1);
                else break;
            }
        }
        return maxFreq;
    }

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5)); // 3
    }
}

Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

After sorting, we can binary search for the maximum frequency L. For a fixed L, we check if any subarray of length L exists such that the cost to make all elements equal to the largest element in that subarray is $\le k$ .

Thought Process

Sort the array.
Search range for frequency L is [1, n].
For each mid length:
- Use a fixed-size sliding window of size mid.
- Cost for window [i, i + mid - 1] is nums[i + mid - 1] * mid - windowSum.
- If any window has cost <= k, mid is possible.
Adjust the search range accordingly.

Pattern: BS on Answer + Rolling Sum

⏱ O(N log N) - Sorting takes $O(N \log N)$, and binary search check takes $O(N)$ for each of the $\log N$ steps.💾 O(1) - Ignored sorting space.

java

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 1, high = nums.length, ans = 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, k, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int[] nums, int k, int len) {
        long currentSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            if (i >= len) currentSum -= nums[i - len];
            if (i >= len - 1) {
                long cost = (long)nums[i] * len - currentSum;
                if (cost <= k) return true;
            }
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Sorting + Sliding Window)

Intuition

Thought Process

After sorting, for any window [left, right], it's always optimal to make all elements equal to the largest element nums[right]. The total cost is nums[right] * windowSize - windowSum. We maintain the largest possible window that satisfies cost <= k.

Patterns

Sort then Window: Sorting allows monotonic cost calculations.
Sum-based Cost: cost = lastVal * len - sum.

⏱ O(N log N)💾 O(1)

Detailed Dry Run

R	Num	Sum	Cost (4*Win - Sum)	Max Freq
0	1	1	0	1
1	2	3	2*2 - 3 = 1	2
2	4	7	4*3 - 7 = 5	3

java

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

    public static void main(String[] args) {
        System.out.println(maxFrequency(new int[]{1, 2, 4}, 5));
    }
}

⚠️ Common Pitfalls & Tips

Integer overflow is a common issue here. nums[right] * (right - left + 1) can exceed 2^31 - 1, so use 64-bit integers (long in Java/C++, default in Python/JS) for intermediate calculations.

← Previous QuestionSubarrays with K Different Integers

Next Question →Longest Substring with At Most K Distinct Characters

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.