Pseudo-code:

text
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)$.

Core Insight for Frequency of the Most Frequent Element

The key intuition relies on the properties of a sorted array. Once nums is sorted, the optimal elements to increment to reach a target value nums[R] are the elements immediately preceding it (nums[R-1], nums[R-2], etc.). These elements are closest in value to nums[R], minimizing the cost of operations.

If we consider a window defined by indices [L, R], we want to treat nums[R] as the target value for all elements in this window. The cost to transform all elements in nums[L...R] to nums[R] can be calculated in $O(1)$ time if we maintain a running sum of the window.

The Condition: To make all elements in the window [L, R] equal to nums[R], the total sum required is nums[R] * window_length. The operations needed (cost) is the difference between this target sum and the actual sum of the elements currently in the window.

$\text{Cost} = (\text{nums}[R] \times (R - L + 1)) - \sum_{i=L}^{R} \text{nums}[i]$

The Invariant: We expand R to try and increase the frequency. If the calculated Cost exceeds k, the window is invalid. We must then increment L to shrink the window from the left, reducing the cost, until the condition is met again.

Visual Description: Imagine the sorted array values plotted as vertical bars on a 2D graph. A sliding window [L, R] selects a range of these bars. The value nums[R] creates a horizontal "ceiling" extending leftwards to L. The empty space between this ceiling and the tops of the bars within [L, R] represents the cost to increment those numbers. As the right pointer moves to a taller bar, the ceiling rises, drastically increasing the empty space (cost). If this empty space area exceeds k, the left pointer moves right, removing the shortest bars from the calculation to reduce the total area.

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.

Reference Implementation

C++ Solution for LeetCode 1838

cpp
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        long long total = 0;
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < nums.size(); ++right) {
            total += nums[right];
            
            // Current window size: right - left + 1
            // Target sum: nums[right] * window_size
            // Operations needed: Target sum - total
            // Use long long for the calculation to avoid overflow
            long long windowSize = right - left + 1;
            long long cost = (long long)nums[right] * windowSize - total;
            
            while (cost > k) {
                total -= nums[left];
                left++;
                // Recalculate cost for the new window size
                windowSize = right - left + 1;
                cost = (long long)nums[right] * windowSize - total;
            }
            
            maxFreq = max(maxFreq, (int)windowSize);
        }
        
        return maxFreq;
    }
};

Java Solution for LeetCode 1838

java
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        
        long total = 0;
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < nums.length; right++) {
            total += nums[right];
            
            // Calculate cost: (target * length) - current_sum
            // Use long to prevent integer overflow
            long target = nums[right];
            long windowLength = right - left + 1;
            
            // While cost exceeds k, shrink window from the left
            while (target * windowLength - total > k) {
                total -= nums[left];
                left++;
                windowLength = right - left + 1;
            }
            
            maxFreq = Math.max(maxFreq, (int)windowLength);
        }
        
        return maxFreq;
    }
}

Python Solution for LeetCode 1838

python
class Solution:
    def maxFrequency(self, nums: list[int], k: int) -> int:
        nums.sort()
        
        left = 0
        total = 0
        max_freq = 0
        
        for right in range(len(nums)):
            total += nums[right]
            
            # Condition: (target * length) - sum <= k
            # Target is nums[right]
            while nums[right] * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            
            max_freq = max(max_freq, right - left + 1)
            
        return max_freq