Frequency of the Most Frequent Element

LeetCode 1838: Frequency of the Most Frequent Element Solution & Explanation

Problem Overview

TL;DR: Sort the input array and use a sliding window to find the longest contiguous subarray where the cost to make all elements equal to the largest element does not exceed k.

In the Frequency of the Most Frequent Element problem, you are provided with an integer array nums and a budget k. You are allowed to increment any element in the array by 1, and each increment costs 1 unit of your budget. The goal is to determine the maximum frequency of any single element possible after performing operations, provided the total cost is less than or equal to k.

This is a popular interview question that tests your ability to optimize brute force logic into linear time complexity using sorting and windowing techniques.

Brute Force Approach for Frequency of the Most Frequent Element

The naive approach involves trying to make every element in the array the "most frequent" target. Since we can only increment numbers (not decrement), it is logical to sort the array first. If we choose an element nums[i] as our target value, we should look at elements smaller than nums[i] (i.e., nums[i-1], nums[i-2], etc.) and increment them to match nums[i] until our budget k is exhausted.

Pseudo-code:

Sort nums
Initialize max_frequency = 1

For i from 0 to length(nums) - 1:
    target = nums[i]
    current_cost = 0
    current_frequency = 1
    
    For j from i - 1 down to 0:
        cost_to_increment = target - nums[j]
        If current_cost + cost_to_increment <= k:
            current_cost += cost_to_increment
            current_frequency += 1
        Else:
            Break inner loop
            
    Update max_frequency with current_frequency

Time Complexity Analysis

The brute force solution requires sorting, which takes $O(N \log N)$. However, the nested loops result in $O(N^2)$ complexity. Given the constraints where $N$ can be up to $10^5$, an $O(N^2)$ algorithm performs roughly $10^{10}$ operations, which will result in a Time Limit Exceeded (TLE) error. We need a solution closer to $O(N \log N)$ or $O(N)$.

Algorithm Strategy: Sliding Window Patterns

1. Sort the Input: Sort nums in ascending order. This ensures that as we iterate, we only consider valid increments (adding to smaller numbers to reach a larger number).
2. Initialize Pointers and State: Set a left pointer L to 0. Maintain a variable total to track the sum of elements in the current window [L, R]. Initialize max_freq to 0.
3. Expand the Window (Right Pointer): Iterate with a right pointer R from 0 to N-1.
   • Add nums[R] to total.
4. Check Constraint and Shrink (Left Pointer):
   • Calculate the cost: (nums[R] * (R - L + 1)) - total.
   • While the cost > k:
     • Subtract nums[L] from total.
     • Increment L.
     • Recalculate cost implicitly in the next check (or logically note the window size reduced).
5. Update Result: After the inner loop (when the window is valid), update max_freq with the current window size R - L + 1.
6. Return Result: Return max_freq.

Execution Flow

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

1. Sort: nums is already [1, 2, 4].
2. Init: L = 0, total = 0, max_freq = 0.
3. Iteration R=0 (Value 1):
   • total becomes 1.
   • Window [1]. Target 1. Length 1.
   • Cost check: 1 * 1 - 1 = 0. $0 \le 5$. Valid.
   • max_freq = max(0, 1) = 1.
4. Iteration R=1 (Value 2):
   • total becomes 1 + 2 = 3.
   • Window [1, 2]. Target 2. Length 2.
   • Cost check: 2 * 2 - 3 = 1. $1 \le 5$. Valid.
   • max_freq = max(1, 2) = 2.
5. Iteration R=2 (Value 4):
   • total becomes 3 + 4 = 7.
   • Window [1, 2, 4]. Target 4. Length 3.
   • Cost check: 4 * 3 - 7 = 5. $5 \le 5$. Valid.
   • max_freq = max(2, 3) = 3.
6. End: Return 3.

Consider nums = [1, 4, 8, 13], k = 5.

1. ...Skip to R=2 (Value 8):
   • Assume window was [4, 8] (indices 1 to 2). total = 12.
   • Target 8. Length 2. Cost 16 - 12 = 4 <= 5. Valid.
2. Iteration R=3 (Value 13):
   • total becomes 12 + 13 = 25.
   • Window [4, 8, 13] (indices 1 to 3). Target 13. Length 3.
   • Cost check: 13 * 3 - 25 = 14. $14 > 5$. Invalid.
   • Shrink: Remove nums[L] (which is 4). total becomes 21. L becomes 2.
   • New Window [8, 13]. Target 13. Length 2.
   • Cost check: 13 * 2 - 21 = 5. $5 \le 5$. Valid.
   • max_freq = max(..., 2).

Proof of Correctness

The algorithm relies on the fact that for any fixed right endpoint R (where nums[R] is the target value), there exists a unique smallest left endpoint L such that the cost to convert nums[L...R] to nums[R] is $\le k$.

Because the array is sorted, adding an element to the left of the window always increases the cost, and removing an element from the left always decreases the cost. This monotonicity allows us to use a sliding window. By iterating R across the entire array and maintaining the optimal L for each R, we exhaustively check the maximum possible frequency ending at every possible position. The global maximum of these local maxima is the correct answer.

Pattern Reuse Notes

The Sliding Window - Variable Size (Condition-Based) pattern is versatile and appears in many standard interview problems.

• LeetCode 3: Longest Substring Without Repeating Characters - Expands right to add characters, shrinks left when a duplicate is found.
• LeetCode 76: Minimum Window Substring - Expands right to cover required characters, shrinks left to minimize length while maintaining validity.
• LeetCode 209: Minimum Size Subarray Sum - Expands right to increase sum, shrinks left to find the minimal length that meets the sum threshold.
• LeetCode 219: Contains Duplicate II - Uses a window (or hash map logic simulating a window) to check for duplicates within a specific distance.

Mastering the mechanics of the "expand-validate-shrink" loop in this problem directly aids in solving these related challenges.

Reference Implementation

C++ Solution for LeetCode 1838

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    int maxFrequency(vector<int>& nums, int k) {
9        sort(nums.begin(), nums.end());
10        
11        long long total = 0;
12        int left = 0;
13        int maxFreq = 0;
14        
15        for (int right = 0; right < nums.size(); ++right) {
16            total += nums[right];
17            
18            // Current window size: right - left + 1
19            // Target sum: nums[right] * window_size
20            // Operations needed: Target sum - total
21            // Use long long for the calculation to avoid overflow
22            long long windowSize = right - left + 1;
23            long long cost = (long long)nums[right] * windowSize - total;
24            
25            while (cost > k) {
26                total -= nums[left];
27                left++;
28                // Recalculate cost for the new window size
29                windowSize = right - left + 1;
30                cost = (long long)nums[right] * windowSize - total;
31            }
32            
33            maxFreq = max(maxFreq, (int)windowSize);
34        }
35        
36        return maxFreq;
37    }
38};

Java Solution for LeetCode 1838

1import java.util.Arrays;
2
3class Solution {
4    public int maxFrequency(int[] nums, int k) {
5        Arrays.sort(nums);
6        
7        long total = 0;
8        int left = 0;
9        int maxFreq = 0;
10        
11        for (int right = 0; right < nums.length; right++) {
12            total += nums[right];
13            
14            // Calculate cost: (target * length) - current_sum
15            // Use long to prevent integer overflow
16            long target = nums[right];
17            long windowLength = right - left + 1;
18            
19            // While cost exceeds k, shrink window from the left
20            while (target * windowLength - total > k) {
21                total -= nums[left];
22                left++;
23                windowLength = right - left + 1;
24            }
25            
26            maxFreq = Math.max(maxFreq, (int)windowLength);
27        }
28        
29        return maxFreq;
30    }
31}

Python Solution for LeetCode 1838

1class Solution:
2    def maxFrequency(self, nums: list[int], k: int) -> int:
3        nums.sort()
4        
5        left = 0
6        total = 0
7        max_freq = 0
8        
9        for right in range(len(nums)):
10            total += nums[right]
11            
12            # Condition: (target * length) - sum <= k
13            # Target is nums[right]
14            while nums[right] * (right - left + 1) - total > k:
15                total -= nums[left]
16                left += 1
17            
18            max_freq = max(max_freq, right - left + 1)
19            
20        return max_freq