Frequency of the Most Frequent Element solution and explanation
Google
Infosys
IBM
9 more videos on this problem
Frequency of the Most Frequent Element - Sliding Window - Leetcode 1838NeetCode · 18:10 · 129K views
Frequency of the Most Frequent Element | Binary Search | Sliding Window | META | Leetcode-1838codestorywithMIK · 57:25 · 34K views
1838. Frequency of the Most Frequent Element | Sliding Window Template | Shrinking & Non-ShrinkingAryan Mittal · 21:09 · 33K views
Frequency of the Most Frequent Element - LeetCode #1838 with python programmingCodingNinja · 15:07 · 12K views
Frequency of the most frequent element | Java | Leetcode | Medium | Sliding Window ModerationAlgorithmHQ · 10:24 · 12K views
LeetCode | 1838. Frequency of the Most Frequent Element | Sliding Window | PrefixSumCompl3x · 17:19 · 7K views
Solving LeetCode 1838 Frequency of the Most Frequent Element | Sliding Window | MetaCode Harmony · 11:43 · 6K views
LeetCode 1838. Frequency of the Most Frequent ElementHappy Coding · 18:47 · 3K views
Leetcode 1838. Frequency of the Most Frequent Element | Logic CodingXian Zhang · 6:33 · 3K views
Leetcode 1838: Frequency of the Most Frequent Element | Java SolutionMaybe Something New · 11:30 · 2K views
The 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 <= 1051 <= nums[i] <= 1051 <= k <= 105
Approach overview
Problem Overview: You are given an integer array and an integer k. In one operation you can increment any element by 1. The goal is to maximize the frequency of some value after performing at most k increments. In other words, determine the largest group of equal numbers you can create by increasing smaller numbers.
Approach 1: Sliding Window Technique (O(n log n) time, O(1) space)
The key observation: if the array is sorted, you only need to raise smaller numbers to match a larger number on the right. After sorting, maintain a sliding window where the right pointer represents the target value all elements should match. Track the running sum of the window. The cost to convert all numbers in the window to nums[right] is nums[right] * window_size - window_sum. If that cost exceeds k, move the left pointer to shrink the window until the cost becomes valid again.
This works because sorting guarantees that increasing elements only moves them toward the current maximum. Each element enters and leaves the window once, so the window scan is linear. The only expensive step is sorting. This approach combines sorting with a classic sliding window pattern to efficiently track the largest feasible group.
Approach 2: Binary Search with Prefix Sums (O(n log n) time, O(n) space)
Another strategy treats the answer (maximum frequency) as a search space. After sorting the array, precompute a prefix sum array so you can quickly calculate the sum of any subarray. Then binary search on the possible frequency f. For each candidate frequency, check whether there exists a window of size f that can be converted to the same value using at most k increments.
To verify a window ending at index i, compute the cost to raise all elements in that window to nums[i]. Using prefix sums, the subarray sum is retrieved in O(1). The required operations become nums[i] * f - window_sum. If any window satisfies the k constraint, that frequency is feasible.
This approach explicitly searches the answer space using binary search. It is slightly more verbose than the sliding window solution but useful when you want a structured way to reason about feasibility problems.
Recommended for interviews: The sliding window approach is the expected solution. It shows you recognize that sorting converts the problem into expanding and shrinking a window based on operation cost. Binary search with prefix sums is also correct but usually considered a secondary method. Demonstrating the sliding window insight signals strong pattern recognition and optimization skills.
Approach 1: Approach 1: Sliding Window Technique
The sliding window technique is used to find the longest subarray where elements can be incremented to make them equal using at most k increments. We sort the array first to ensure it's easier to increment elements to become equal. We then use two pointers: one for the current end of the subarray and the other to represent the start. By checking the cost to transform the current subarray into an equal value using the difference between values and leveraging the sorted property, we can determine the maximum frequency we can achieve.
class Solution:
def maxFrequency(self, nums, k):
nums.sort()
sum = 0
left = 0
res = 0
for right in range(len(nums)):
sum += nums[right]
while nums[right] * (right - left + 1) > sum + k:
sum -= nums[left]
left += 1
res = max(res, right - left + 1)
return res
# Sample Usage
sol = Solution()
print(sol.maxFrequency([1, 2, 4], 5))import java.util.Arrays;
public class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
long sum = 0;
int left = 0, res = 0;
for (int right = 0; right < nums.length; ++right) {
sum += nums[right];
while (nums[right] * (right - left + 1L) > sum + k) {
sum -= nums[left++];
}
res = Math.max(res, right - left + 1);
}
return res;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 4};
int k = 5;
System.out.println(sol.maxFrequency(nums, k));
}
}#include <vector>
#include <algorithm>
#include <numeric>
class Solution {
public:
int maxFrequency(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
long long sum = 0;
int left = 0, res = 0;
for (int right = 0; right < nums.size(); ++right) {
sum += nums[right];
while (nums[right] * (right - left + 1LL) > sum + k) {
sum -= nums[left++];
}
res = std::max(res, right - left + 1);
}
return res;
}
};
// Sample Usage
#include <iostream>
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 4};
int k = 5;
std::cout << sol.maxFrequency(nums, k) << std::endl;
return 0;
}function maxFrequency(nums, k) {
nums.sort((a, b) => a - b);
let sum = 0;
let left = 0;
let res = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (nums[right] * (right - left + 1) > sum + k) {
sum -= nums[left++];
}
res = Math.max(res, right - left + 1);
}
return res;
}
// Sample Usage
console.log(maxFrequency([1, 2, 4], 5));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int maxFrequency(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
long long sum = 0;
int left = 0;
int res = 0;
for (int right = 0; right < numsSize; ++right) {
sum += nums[right];
while (nums[right] * (right - left + 1LL) > sum + k) {
sum -= nums[left++];
}
res = (res < right - left + 1) ? right - left + 1 : res;
}
return res;
}
int main() {
int nums[] = {1, 2, 4};
int k = 5;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxFrequency(nums, size, k));
return 0;
}using System;
public class Solution {
public int MaxFrequency(int[] nums, int k) {
Array.Sort(nums);
long sum = 0;
int left = 0, res = 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() {
Solution sol = new Solution();
Console.WriteLine(sol.MaxFrequency(new int[] { 1, 2, 4 }, 5));
}
}The Python solution sorts the list and maintains a sliding window using sum calculations to determine the possible maximum equal frequency within a boundary condition constrained by k. It effectively tracks and updates the maximum range by adjusting the left pointer as necessary.
Time Complexity: O(n log n), due to sort operation.
Space Complexity: O(1), considering no additional data structures are substantially utilized.
Approach 2: Approach 2: Binary Search with Prefix Sums
This approach makes use of binary search in combination with prefix sums to efficiently find the maximum frequency possible by transforming elements. We first sort the array. For a given target frequency, we check through calculating the required increment operations using a prefix sum array and binary searching over possible solutions. This allows us to leverage efficient range queries and reduce time complexity.
class Solution:
def maxFrequency(self, nums, k):
nums.sort()
prefix_sum = [0] * len(nums)
for i in range(len(nums)):
prefix_sum[i] = prefix_sum[i - 1] + nums[i] if i > 0 else nums[i]
def can_achieve(freq):
for end in range(freq - 1, len(nums)):
required = nums[end] * freq
if required - (prefix_sum[end] - (prefix_sum[end - freq] if end >= freq else 0)) <= k:
return True
return False
left, right, res = 1, len(nums), 1
while left <= right:
mid = (left + right) // 2
if can_achieve(mid):
res = mid
left = mid + 1
else:
right = mid - 1
return res
# Sample Usage
sol = Solution()
print(sol.maxFrequency([1, 2, 4], 5))import java.util.Arrays;
public class Solution {
private boolean canAchieveFrequency(int[] nums, int freq, int k, long[] prefixSum) {
for (int end = freq - 1; end < nums.length; ++end) {
long totalNeeded = (long)nums[end] * freq;
long currentSum = prefixSum[end] - (end - freq >= 0 ? prefixSum[end - freq] : 0);
if (totalNeeded - currentSum <= k) return true;
}
return false;
}
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
long[] prefixSum = new long[nums.length];
for (int i = 0; i < nums.length; ++i) {
prefixSum[i] = (i > 0 ? prefixSum[i - 1] : 0) + nums[i];
}
int left = 1, right = nums.length, res = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieveFrequency(nums, mid, k, prefixSum)) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 4};
int k = 5;
System.out.println(sol.maxFrequency(nums, k));
}
}#include <vector>
#include <algorithm>
#include <numeric>
class Solution {
public:
bool canAchieveFrequency(std::vector<int>& nums, int freq, int k, std::vector<long long>& prefixSum) {
for (int end = freq - 1; end < nums.size(); ++end) {
long long totalNeeded = (long long)nums[end] * freq;
long long currentSum = prefixSum[end] - (end - freq >= 0 ? prefixSum[end - freq] : 0);
if (totalNeeded - currentSum <= k) return true;
}
return false;
}
int maxFrequency(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
std::vector<long long> prefixSum(nums.size());
std::partial_sum(nums.begin(), nums.end(), prefixSum.begin());
int left = 1, right = nums.size(), res = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieveFrequency(nums, mid, k, prefixSum)) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
};
// Sample Usage
#include <iostream>
int main() {
Solution sol;
std::vector<int> nums = {1, 2, 4};
int k = 5;
std::cout << sol.maxFrequency(nums, k) << std::endl;
return 0;
}function maxFrequency(nums, k) {
nums.sort((a, b) => a - b);
const prefixSum = new Array(nums.length).fill(0);
nums.reduce((sum, num, idx) => {
prefixSum[idx] = sum + num;
return prefixSum[idx];
}, 0);
function canAchieveFrequency(freq) {
for (let end = freq - 1; end < nums.length; end++) {
const totalNeeded = nums[end] * freq;
const currentSum = prefixSum[end] - (end >= freq ? prefixSum[end - freq] : 0);
if (totalNeeded - currentSum <= k) return true;
}
return false;
}
let left = 1, right = nums.length, res = 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canAchieveFrequency(mid)) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
// Sample Usage
console.log(maxFrequency([1, 2, 4], 5));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
long long getPrefixSum(int* prefixSum, int i) {
return i >= 0 ? prefixSum[i] : 0;
}
int canAchieveFrequency(int* nums, int numsSize, int freq, int k, int* prefixSum) {
for (int end = freq - 1; end < numsSize; ++end) {
long long required = (long long)nums[end] * freq - (getPrefixSum(prefixSum, end) - getPrefixSum(prefixSum, end - freq));
if (required <= k) return 1;
}
return 0;
}
int maxFrequency(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
int* prefixSum = (int*)malloc(numsSize * sizeof(int));
prefixSum[0] = nums[0];
for (int i = 1; i < numsSize; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
int left = 1, right = numsSize, res = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canAchieveFrequency(nums, numsSize, mid, k, prefixSum)) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
free(prefixSum);
return res;
}
int main() {
int nums[] = {1, 2, 4};
int k = 5;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxFrequency(nums, size, k));
return 0;
}using System;
public class Solution {
bool CanAchieveFrequency(int[] nums, int freq, int k, long[] prefixSum) {
for (int end = freq - 1; end < nums.Length; ++end) {
long totalNeeded = (long)nums[end] * freq;
long currentSum = prefixSum[end] - (end - freq >= 0 ? prefixSum[end - freq] : 0);
if (totalNeeded - currentSum <= k) return true;
}
return false;
}
public int MaxFrequency(int[] nums, int k) {
Array.Sort(nums);
long[] prefixSum = new long[nums.Length];
for (int i = 0; i < nums.Length; ++i) {
prefixSum[i] = (i > 0 ? prefixSum[i - 1] : 0) + nums[i];
}
int left = 1, right = nums.Length, res = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanAchieveFrequency(nums, mid, k, prefixSum)) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MaxFrequency(new int[] { 1, 2, 4 }, 5));
}
}The Python code efficiently utilizes sorting and binary search to scan through possible frequencies. By organizing prefix sums, it ensures quick calculation of how many increments are necessary to achieve uniform elements over a subarray, respecting the operations limit.
Time Complexity: O(n log n), searching viable frequencies involves sorting and binary exploration.
Space Complexity: O(n), space allocated for prefix sums.
Approach 3: Sorting + Prefix Sum + Binary Search
According to the problem description, we can draw three conclusions:
- After several operations, the element with the highest frequency in the array must be an element in the original array. Why? Suppose the elements operated are
a_1, a_2, cdots, a_m, where the maximum isa_m. These elements have all been changed to the same valuex, wherex geq a_m. Then we can also change these elements all toa_m, and the number of operations will not increase. - The elements operated must be a continuous subarray in the sorted array.
- If a frequency
msatisfies the condition, then allm' < malso satisfy the condition. This inspires us to consider using binary search to find the maximum frequency that satisfies the condition.
Therefore, we can sort the array nums and then calculate the prefix sum array s of the sorted array, where s[i] represents the sum of the first i elements.
Next, we define the left boundary of the binary search as l = 1, and the right boundary as r = n. For each binary search, we take the middle value m = (l + r + 1) / 2, and then check whether there exists a continuous subarray of length m such that all elements in the subarray can be changed to an element in the array, and the number of operations does not exceed k. If such a subarray exists, we can update the left boundary l to m, otherwise update the right boundary r to m - 1.
Finally, return the left boundary l.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
function maxFrequency(nums: number[], k: number): number {
const n = nums.length;
nums.sort((a, b) => a - b);
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
let [l, r] = [1, n];
const check = (m: number): boolean => {
for (let i = m; i <= n; ++i) {
if (nums[i - 1] * m - (s[i] - s[i - m]) <= k) {
return true;
}
}
return false;
};
while (l < r) {
const mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maxFrequency(nums []int, k int) int {
n := len(nums)
sort.Ints(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
check := func(m int) bool {
for i := m; i <= n; i++ {
if nums[i-1]*m-(s[i]-s[i-m]) <= k {
return true
}
}
return false
}
l, r := 1, n
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}Approach 4: Sorting + Two Pointers
We can also use two pointers to maintain a sliding window, where all elements in the window can be changed to the maximum value in the window. The number of operations for the elements in the window is s, and s leq k.
Initially, we set the left pointer j to point to the first element of the array, and the right pointer i also points to the first element of the array. Next, we move the right pointer i each time, changing all elements in the window to nums[i]. At this time, the number of operations to be increased is (nums[i] - nums[i - 1]) times (i - j). If this number of operations exceeds k, then we need to move the left pointer j until the number of operations for the elements in the window does not exceed k. Then, we update the answer to the maximum length of the window.
The time complexity is O(n log n), and the space complexity is O(log n). Where n is the length of the array nums.
function maxFrequency(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
let ans = 1;
let [s, j] = [0, 0];
for (let i = 1; i < nums.length; ++i) {
s += (nums[i] - nums[i - 1]) * (i - j);
while (s > k) {
s -= nums[i] - nums[j++];
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}func maxFrequency(nums []int, k int) int {
sort.Ints(nums)
ans := 1
s := 0
for i, j := 1, 0; i < len(nums); i++ {
s += (nums[i] - nums[i-1]) * (i - j)
for ; s > k; j++ {
s -= nums[i] - nums[j]
}
ans = max(ans, i-j+1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sliding Window Technique | Time Complexity: O(n log n), due to sort operation. Space Complexity: O(1), considering no additional data structures are substantially utilized. |
| Approach 2: Binary Search with Prefix Sums | Time Complexity: O(n log n), searching viable frequencies involves sorting and binary exploration. Space Complexity: O(n), space allocated for prefix sums. |
| Sorting + Prefix Sum + Binary Search | – |
| Sorting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Sorting | O(n log n) | O(1) | Best general solution; efficient after sorting and commonly expected in interviews |
| Binary Search with Prefix Sums | O(n log n) | O(n) | Useful when treating frequency as a search space and validating ranges quickly |
Frequently asked questions
Is Frequency of the Most Frequent Element easy or hard?
Frequency of the Most Frequent Element is generally rated as a Medium problem. The difficulty comes from recognizing that sorting plus a sliding window can track the cost of equalizing numbers efficiently.
Frequency of the Most Frequent Element Python/Java solution
Most implementations follow the same pattern: sort the array, maintain two pointers, track the running sum of the window, and ensure the increment cost does not exceed k. This logic translates directly into Python, Java, C++, C#, and JavaScript with identical time complexity of O(n log n).
How to solve Frequency of the Most Frequent Element in O(n)?
Pure O(n) is not possible for arbitrary input because you must compare relative ordering of elements. The standard method sorts the array first and then uses a sliding window to maintain the largest valid range. The resulting complexity is O(n log n) time and O(1) space.
What is the best approach for Frequency of the Most Frequent Element?
The sliding window approach after sorting the array is the most efficient and commonly used solution. Maintain a window where all values are raised to match the rightmost element and track the cost using the window sum. If the required increments exceed k, shrink the window from the left. This runs in O(n log n) time due to sorting and O(1) extra space.
Is Frequency of the Most Frequent Element asked at Google/Amazon/Meta?
Frequency of the Most Frequent Element is a common interview-style problem that appears in large tech company question sets including Amazon, Google, and Meta-style practice lists. It tests sliding window optimization, greedy reasoning, and understanding of prefix sums or cost calculations.
What data structure is used in Frequency of the Most Frequent Element?
The solution mainly uses arrays with sorting and a sliding window implemented using two pointers. Some variations also use prefix sums to compute subarray totals quickly when combined with binary search.
What is the time complexity of Frequency of the Most Frequent Element?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, the sliding window scan processes each element at most twice, giving an O(n) pass. Space complexity is O(1) if you track the running sum instead of building auxiliary arrays.