Brute Force Approach for Maximum Frequency of an Element After Performing Operations I

The naive approach involves iterating through every possible target value and counting how many numbers can be converted to it.

1. Identify the range of values in nums. The potential target values lie roughly between $\min(nums) - k$ and $\max(nums) + k$.
2. Iterate through every integer $X$ in this range.
3. For each $X$, iterate through the entire nums array.
4. Count how many elements $n$ satisfy $|n - X| \le k$. Let this count be $C$.
5. Count how many elements are already equal to $X$. Let this be $F$.
6. The achievable frequency for $X$ is $\min(C, F + \text{numOperations})$.
7. Track the maximum frequency found.

Pseudo-code:

python
max_freq = 0
min_val, max_val = min(nums), max(nums)
# Iterate all possible targets
for target in range(min_val - k, max_val + k + 1):
    count_in_range = 0
    count_exact = 0
    for n in nums:
        if abs(n - target) <= k:
            count_in_range += 1
        if n == target:
            count_exact += 1
    
    # We can convert at most numOperations elements that aren't already target
    achievable = min(count_in_range, count_exact + numOperations)
    max_freq = max(max_freq, achievable)

Why it fails: The values in nums can be up to $10^5$, and k can also be $10^5$. The range of potential targets is roughly $3 \times 10^5$. With nums.length up to $10^5$, the nested loop results in roughly $3 \cdot 10^{10}$ operations. This results in a Time Limit Exceeded (TLE) error.

Core Insight for Maximum Frequency of an Element After Performing Operations I

The key intuition is to invert the problem: instead of picking a target and finding compatible numbers, let's look at the numbers and see what targets they support.

1. Transformation Range: A number n can become any value in the interval [n - k, n + k].
2. Intersection: If we want a set of numbers to all become the same target $X$, their transformation ranges must all overlap at $X$.
3. Sorted Array Property: If we sort nums, any set of numbers that can converge to a single value will appear consecutively in the array.
4. The Constraint: For a window of numbers nums[left...right] to be convertible to some common target $X$, the difference between the largest and smallest number in the window must be small enough. Specifically, nums[right] - nums[left] <= 2 * k.
5. Two Scenarios:
   • Scenario A (Ghost Target): The optimal target $X$ is not originally in nums. In this case, we have 0 initial occurrences. We can convert at most numOperations elements. The answer is bounded by numOperations.
   • Scenario B (Existing Target): The optimal target $X$ is a value already present in nums. Here, we can keep all instances of $X$ (cost 0) and convert numOperations neighbors. The answer is bounded by .

We need to check the maximum density of intervals using a sliding window to satisfy both scenarios.

Execution Flow

Let nums = [1, 4, 5], k = 1, numOperations = 2. Sorted nums: [1, 4, 5]. Frequencies: {1:1, 4:1, 5:1}.

Step 1: Generic Window Check (diff <= 2k)

• 2k = 2.
• [1]: Valid. Len 1. Max = min(1, 2) = 1.
• [1, 4]: $4-1=3 > 2$. Invalid. Shrink left.
• [4]: Valid. Len 1. Max = 1.
• [4, 5]: $5-4=1 \le 2$. Valid. Len 2. Max = min(2, 2) = 2.
• Result so far: 2.

Step 2: Centered Window Check (Target = nums[i])

• Target 1: Range [0, 2]. Elements in nums within this range: [1]. Count = 1.
  • freq[1] = 1.
  • Possible: min(1, 1 + 2) = 1.
• Target 4: Range [3, 5]. Elements in nums within this range: [4, 5]. Count = 2.
  • freq[4] = 1.
  • Possible: min(2, 1 + 2) = 2.
• Target 5: Range [4, 6]. Elements in nums within this range: [4, 5]. Count = 2.
  • freq[5] = 1.
  • Possible: min(2, 1 + 2) = 2.

Final Result: 2.

Proof of Correctness

The algorithm relies on the fact that the optimal target $X$ must either be one of the values in nums or a value that maximizes the overlap of intervals $[n-k, n+k]$.

1. If the optimal target is in nums, the "Centered Window" check explicitly calculates the max frequency by counting neighbors in $[X-k, X+k]$ and applying the numOperations cap correctly (preserving existing $X$s).
2. If the optimal target is not in nums, it implies we are purely relying on converting numbers. The "Generic Window" check finds the densest cluster of size $\le 2k$. Any window satisfying nums[right] - nums[left] <= 2k can theoretically converge to the midpoint. Since the target doesn't exist initially, the max frequency is simply the window size capped by numOperations.
3. Taking the maximum of these two cases covers all possibilities.

Reference Implementation

C++ Solution for LeetCode 3346

cpp
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        map<int, int> freq;
        for (int x : nums) freq[x]++;
        
        int n = nums.size();
        int maxFreq = 0;
        
        // Strategy 1: Generic Sliding Window
        // Finds max elements that can converge to *some* target (limited by numOperations)
        int left = 0;
        for (int right = 0; right < n; ++right) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            // If we pick a target not in nums, we can at most have numOperations
            maxFreq = max(maxFreq, min(right - left + 1, numOperations));
        }
        
        // Strategy 2: Centered Sliding Window
        // Checks specific targets existing in nums
        left = 0;
        int right = 0;
        // Iterate through unique numbers to use as centers
        for (auto const& [val, count] : freq) {
            // Find window covering range [val - k, val + k]
            while (right < n && nums[right] <= val + k) {
                right++;
            }
            while (left < n && nums[left] < val - k) {
                left++;
            }
            
            int countInRange = right - left;
            // We can keep 'count' existing elements + convert up to 'numOperations' others
            maxFreq = max(maxFreq, min(countInRange, count + numOperations));
        }
        
        return maxFreq;
    }
};

Java Solution for LeetCode 3346

java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        int n = nums.length;
        int maxFreq = 0;
        
        // Strategy 1: Generic Sliding Window
        // Maximize window where nums[right] - nums[left] <= 2*k
        int left = 0;
        for (int right = 0; right < n; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            // Limited by numOperations because the target might not exist in nums
            maxFreq = Math.max(maxFreq, Math.min(right - left + 1, numOperations));
        }
        
        // Strategy 2: Check ranges centered on existing numbers
        left = 0;
        int right = 0;
        // We iterate through the sorted unique keys implicitly by scanning nums
        // But to be efficient, we scan the sorted array and trigger checks per unique value
        for (int i = 0; i < n; ) {
            int val = nums[i];
            int count = freq.get(val);
            
            // Expand right bound for range [val - k, val + k]
            while (right < n && nums[right] <= val + k) {
                right++;
            }
            // Contract left bound
            while (left < n && nums[left] < val - k) {
                left++;
            }
            
            int countInRange = right - left;
            maxFreq = Math.max(maxFreq, Math.min(countInRange, count + numOperations));
            
            // Skip to next unique number
            i += count;
        }
        
        return maxFreq;
    }
}

Python Solution for LeetCode 3346

python
from collections import Counter

class Solution:
    def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
        nums.sort()
        freq = Counter(nums)
        n = len(nums)
        max_freq = 0
        
        # Strategy 1: Generic Sliding Window
        # Find longest subarray where max - min <= 2*k
        left = 0
        for right in range(n):
            while nums[right] - nums[left] > 2 * k:
                left += 1
            # If target is arbitrary, we are capped by numOperations
            max_freq = max(max_freq, min(right - left + 1, numOperations))
            
        # Strategy 2: Target is an existing number in nums
        # We need to count elements in [val - k, val + k]
        left = 0
        right = 0
        
        # Iterate through unique values in sorted order
        unique_vals = sorted(freq.keys())
        
        for val in unique_vals:
            count = freq[val]
            
            # Slide window to cover [val - k, val + k]
            while right < n and nums[right] <= val + k:
                right += 1
            while left < n and nums[left] < val - k:
                left += 1
            
            count_in_range = right - left
            # We can keep existing 'count' and add 'numOperations' neighbors
            max_freq = max(max_freq, min(count_in_range, count + numOperations))
            
        return max_freq