Most Frequent Element LeetCode 1838

LeetCode 1838 — Frequency of the Most Frequent Element — gives you an integer array nums and an integer k. Your goal is to return the maximum possible frequency of any element after performing at most k increment operations.

You can only increment elements, never decrement them. Each increment operation increases one element by exactly 1. You want to pick a target value and bring as many elements as possible up to that target within the k budget.

The key constraint is direction: you can only move elements upward. This one-directional rule is what makes sorting the natural first step — once sorted, every element to the left of a target is a candidate to increment up to it.

The algorithm begins by sorting nums. After sorting, all elements are in non-decreasing order, which means any window of consecutive elements represents a set of values where the largest is nums[right] — the cheapest possible target for the window.

Maintain a sliding window with pointers left and right. As right expands, compute the cost to make all elements in the window equal to nums[right]: cost = (right - left + 1) * nums[right] - windowSum. If this cost exceeds k, shrink the window from the left by incrementing left and subtracting nums[left] from windowSum.

After each adjustment, the window size (right - left + 1) represents the maximum frequency achievable with nums[right] as the target. Track the global maximum of this value across all positions of right.

The cost formula is the mathematical heart of the algorithm. For a window spanning indices left to right with target value nums[right], the total increments needed equals: windowSize * nums[right] - sum(window).

This works because if all elements were already equal to nums[right], their sum would be windowSize * nums[right]. The actual sum of the window is windowSum. The difference is precisely how many total increment operations are required to equalize them.

If cost <= k the window is valid and the frequency is right - left + 1. If cost > k we shrink by moving left forward, removing nums[left] from windowSum, until the window becomes affordable again.

Without sorting, finding the optimal target value would require trying every unique value in nums as a potential target, then scanning the entire array to determine which elements could be incremented to match — an O(n^2) or worse approach.

After sorting, the target is always nums[right] — the maximum value in the current window. Every element to the left is smaller or equal, making them valid candidates for incrementing upward to the target. We never need to consider incrementing right to match something smaller because that would require a decrement.

Sorting also ensures the window contains the elements that are closest in value to the target. Elements just below nums[right] are the cheapest to equalize. Any other subset of the array would include elements farther from the target, costing more increments for the same window size.

Consider nums = [1, 2, 4], k = 5. After sorting the array is already [1, 2, 4]. We process right = 0: windowSum = 1, cost = 1*1 - 1 = 0, freq = 1. right = 1: windowSum = 3, cost = 2*2 - 3 = 1, freq = 2.

right = 2: windowSum = 7, cost = 3*4 - 7 = 5. Since 5 <= k = 5, the window [1, 2, 4] is valid. The frequency is 3 — all three elements can be made equal to 4 using exactly 5 increments (increment 1 three times and 2 twice).

The algorithm returns 3, the maximum possible. All three elements become 4 with the full k budget: element at index 0 needs +3, element at index 1 needs +2, element at index 2 needs +0. Total = 5 = k.

In Python: sort nums, initialize left = 0 and window_sum = 0. Iterate right from 0 to len(nums)-1. Add nums[right] to window_sum. While (right - left + 1) * nums[right] - window_sum > k, subtract nums[left] from window_sum and increment left. Update max_freq. Time complexity is O(n log n) for the sort; the window traversal is O(n) since left only moves forward. Space is O(1) beyond the sort.

In Java: the same approach with a long variable for windowSum to prevent overflow. Sort with Arrays.sort(nums). The left pointer only ever moves forward — the window never truly shrinks below its maximum size because once we find a valid window of size s, we never need to consider windows smaller than s for any future right.

The sliding window here has a subtle property: left never needs to move backward, and the window size is monotonically non-decreasing once it reaches its maximum. This means the algorithm is genuinely O(n) after the sort — left and right together traverse the array at most once.

The budget sliding window pattern — where you expand right, track a cost, and shrink left when cost exceeds a limit — appears in several closely related problems. Minimum Size Subarray Sum asks for the smallest window whose sum meets a threshold. Max Consecutive Ones III allows k flips from 0 to 1, making the cost the number of zeros in the window.

Longest Repeating Character Replacement (LeetCode 424) is perhaps the most similar: you want the longest window where replacing at most k characters makes all characters the same. The cost formula there is windowSize - maxCount, analogous to windowSize * target - windowSum here.

Recognizing the budget window family means you can apply the same left-pointer shrink logic across all these problems. The key pattern: expand right, compute cost, if cost > budget then shrink left, track window size. Mastering LeetCode 1838 gives you fluency across the entire family.