Frequency of the Most Frequent Element — LC 1838 Sort + Sliding Window

Problem Statement#

Given an integer array nums and integer k, you may increment any element by 1 up to k times total. Return the maximum frequency reachable for any value.

Constraints:

• 1 less than or equal to nums.length less than or equal to 10 to the 5
• 1 less than or equal to nums[i] less than or equal to 10 to the 5
• 1 less than or equal to k less than or equal to 10 to the 5

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

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

Why This Problem Matters#

LeetCode 1838 — Frequency of the Most Frequent Element is asked at Google, Amazon, and Citadel because it forces candidates to combine three skills: sorting as a preprocessing step, running-sum maintenance, and the variable-size sliding window. Each step is straightforward in isolation, but coordinating them is what trips up mid-level candidates.

The key reformulation — "after sorting, the optimal target value for any window is the rightmost element" — is the kind of greedy insight interviewers explicitly grade for. If you can prove that, you have demonstrated maturity beyond template execution.

In production, this maps to "make the largest cluster homogeneous within budget" problems: leveling resource allocations, snapping noisy sensor reads to a common value, or maximizing matched bidder counts within a price bump budget.

The Core Insight#

After sorting nums, consider any window [left, right]. The cheapest way to make all elements in the window equal is to lift them all to nums[right], the largest value in the window. The total cost is:

cost equals nums[right] times window_length minus sum(nums[left..right])

Maintain a running window sum. While cost greater than k, advance left and subtract nums[left]. The window length when valid is a candidate answer; track the maximum.

Why does targeting nums[right] dominate any internal target? Lifting to a smaller in-window value would still require lifting elements above it, but you can only increment, not decrement, so any target less than nums[right] is infeasible. Any target greater than nums[right] strictly increases cost. So nums[right] is optimal.

Visual Dry Run#

Input: nums = [1, 2, 4], k = 5. Sorted: [1, 2, 4].

Answer: 3.

Solution (Optimal)#

class Solution:
    def maxFrequency(self, nums, k):
        nums.sort()
        left, total, best = 0, 0, 1
        for right, value in enumerate(nums):
            total += value
            while value * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            best = max(best, right - left + 1)
        return best

var maxFrequency = function(nums, k) {
    nums.sort((a, b) => a - b);
    let left = 0, total = 0, best = 1;
    for (let right = 0; right < nums.length; right++) {
        total += nums[right];
        while (nums[right] * (right - left + 1) - total > k) {
            total -= nums[left];
            left++;
        }
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
};

Time: O(n log n) — sort dominates the linear sliding window. Space: O(1) auxiliary, ignoring sort overhead.

Common Mistakes#

• Forgetting to sort first. The greedy lift-to-max argument requires monotonic order.
• Computing cost with multiplication overflow on large windows. Use 64-bit arithmetic.
• Targeting the leftmost element instead of the rightmost. Decrements are not allowed.
• Using right - left instead of right - left + 1 for window length.
• Not maintaining the running sum and recomputing per iteration, blowing time complexity to O(n squared).

Interview Tips#

• Sort first and explain why: "Lifting to the max is always optimal."
• Derive the cost formula on the whiteboard: nums[right] * window_length - window_sum.
• Mention overflow risk: with n equal to 10 to the 5 and values up to 10 to the 5, products can hit 10 to the 10. Use 64-bit.
• Highlight the invariant: "After shrinking, every prefix of the window can be lifted within budget."
• If asked, mention binary search on answer as an alternative O(n log n) solution.

Follow-up Questions#

• What if you can also decrement? The optimal target becomes the median of the window.
• What if costs are weighted (some elements cost more to increment)? Switch to a heap or priority window.
• Return the element that achieves the max frequency. Track nums[right] at the optimal window.
• What if k can be 0? The answer is the max raw frequency in the array.
• Streaming variant where elements arrive online? Maintain a sorted multiset and a running sum.

Key Takeaways#

• LeetCode 1838 — Frequency of the Most Frequent Element solves in O(n log n) time, O(1) space after sorting.
• After sorting, lifting all window elements to the rightmost value is provably optimal because decrements are not allowed.
• Cost formula: nums[right] * window_length - window_sum.
• Maintain a running sum to keep the inner shrink amortized O(1).
• Watch for 64-bit overflow on nums[right] * window_length.
• Asked at Google, Amazon, and Citadel in mid-loop array rounds.
• Same template extends to LC 1648 (Sell Diminishing-Valued Colored Balls) and LC 1283 (Find Smallest Divisor Given a Threshold).