Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 <= 105Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Greedy · Sliding Window
[1,2,4] 5
[1,4,8,13] 5
[3,9,6] 2
find-all-lonely-numbers-in-the-array)longest-nice-subarray)apply-operations-to-maximize-frequency-score)maximum-frequency-of-an-element-after-performing-operations-i)maximum-frequency-of-an-element-after-performing-operations-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1838: Frequency of the Most Frequent Element
class Solution {
private int[] nums;
private long[] s;
private int k;
public int maxFrequency(int[] nums, int k) {
this.k = k;
this.nums = nums;
Arrays.sort(nums);
int n = nums.length;
s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + nums[i - 1];
}
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int m) {
for (int i = m; i <= nums.length; ++i) {
if (1L * nums[i - 1] * m - (s[i] - s[i - m]) <= k) {
return true;
}
}
return false;
}
}
// Accepted solution for LeetCode #1838: Frequency of the Most Frequent Element
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
}
# Accepted solution for LeetCode #1838: Frequency of the Most Frequent Element
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
def check(m: int) -> bool:
for i in range(m, n + 1):
if nums[i - 1] * m - (s[i] - s[i - m]) <= k:
return True
return False
n = len(nums)
nums.sort()
s = list(accumulate(nums, initial=0))
l, r = 1, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return l
// Accepted solution for LeetCode #1838: Frequency of the Most Frequent Element
impl Solution {
pub fn max_frequency(mut nums: Vec<i32>, k: i32) -> i32 {
let (mut left, mut right, mut res, mut total) = (0, 0, 0, 0);
nums.sort_unstable();
while right < nums.len() {
total += nums[right];
while (nums[right] * (right - left + 1) as i32) - total > k {
total -= nums[left];
left += 1;
}
res = res.max(right - left + 1);
right += 1;
}
res as i32
}
}
// Accepted solution for LeetCode #1838: Frequency of the Most Frequent Element
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;
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.