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

A naive approach would be to iterate through every possible integer that could serve as the target value $X$. Since the values in nums can be up to $10^9$ and k is also large, the potential range for $X$ spans roughly from $\min(nums) - k$ to $\max(nums) + k$.

For each candidate target $X$, we would iterate through the entire nums array to count:

1. How many elements are already equal to $X$.
2. How many elements are not equal to $X$ but can be converted to $X$ (i.e., $|nums[i] - X| \le k$).

We would then calculate the achievable frequency as count(equal) + min(count(convertible), numOperations) and track the maximum.

python
# Pseudo-code for Brute Force
max_freq = 0
min_val = min(nums) - k
max_val = max(nums) + k

for target in range(min_val, max_val + 1):
    equal_count = 0
    convertible_count = 0
    for x in nums:
        if x == target:
            equal_count += 1
        elif abs(x - target) <= k:
            convertible_count += 1
    
    current_freq = equal_count + min(convertible_count, numOperations)
    max_freq = max(max_freq, current_freq)

Time Complexity Analysis: The range of values can be up to $2 \cdot 10^9$. For each value, we iterate nums (size $N$). This results in $O(Range \cdot N)$, which is astronomically large and will instantly receive a Time Limit Exceeded (TLE) verdict.

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

The key intuition is to invert the problem: instead of checking every integer $X$, we look at the constraints imposed by the input numbers.

1. Sorting: By sorting nums, we ensure that if index $i$ and index $j$ can both reach a target $X$, then all indices between $i$ and $j$ can also likely reach $X$ (or are at least closer to doing so).

2. Intersection of Intervals: For a number nums[i] to be convertible to $X$, $X$ must lie in [nums[i] - k, nums[i] + k]. Conversely, if we select a window of elements nums[L...R], they can all be converted to a common target $X$ only if their reachable intervals intersect. This intersection is non-empty if and only if: $nums[R]$ If this condition holds, there exists at least one value (specifically in the range ) that all elements in the window can reach.

3. Two Cases for Optimization:

   • Case A (New Target): The optimal target $X$ is a value not present in nums. Here, the frequency is limited purely by numOperations. We simply need the largest window satisfying $nums[R] - nums[L] \le 2k$. The result is .

Visual Description: Imagine the sorted nums array on a number line. Each element nums[i] projects a segment of width $2k$ centered at itself. We are looking for a point on the number line covered by the maximum number of these segments.

• For Case A, we slide a window of fixed physical width $2k$ over the points. The "Variable Size Sliding Window" on indices expands Right and contracts Left to maintain the condition that the difference between the largest and smallest element in the window is $\le 2k$.
• For Case B, we center our view on each unique nums[i] and expand outwards to find how many neighbors fall within distance $k$.

Execution Flow

Let's trace Example 1: nums = [1, 4, 5], k = 1, numOperations = 2.

1. Sort: nums is already [1, 4, 5].
2. Phase 1 (Generic Window):
   • L=0, R=0: nums[0]-nums[0] = 0 <= 2. Size 1. ans = min(1, 2) = 1.
   • L=0, R=1: nums[1]-nums[0] = 3 > 2. Shrink L.
   • L=1, R=1: nums[1]-nums[1] = 0 <= 2. Size 1. ans = max(1, 1) = 1.
   • L=1, R=2: nums[2]-nums[1] = 1 <= 2. Size 2. ans = max(1, min(2, 2)) = 2.
   • Phase 1 result: 2.
3. Phase 2 (Specific Targets):
   • Target 1: Range $[0, 2]$. Elements in range: [1]. Total 1. Count of 1 is 1. min(1, 1 + 2) = 1.
   • Target 4: Range $[3, 5]$. Elements in range: [4, 5]. Total 2. Count of 4 is 1. min(2, 1 + 2) = 2.
   • Target 5: Range $[4, 6]$. Elements in range: [4, 5]. Total 2. Count of 5 is 1. min(2, 1 + 2) = 2.
   • Phase 2 result: 2.
4. Final Answer: 2.

Proof of Correctness

The algorithm is correct because the optimal target value $X$ must fall into one of two categories:

1. $X$ is a value present in nums. Phase 2 explicitly checks every such candidate. For a fixed $X$, the set of convertible elements is exactly $\{y \in nums \mid X-k \le y \le X+k\}$. We calculate the size of this set and cap the gain by count(X) + numOperations.
2. $X$ is not present in nums. In this case, count(X) = 0. The formula simplifies to min(convertible_count, numOperations). Phase 1 finds the maximum possible convertible_count for any valid $X$ (which corresponds to an interval of size $2k$) and applies the numOperations cap. Since $$ is the necessary and sufficient condition for the existence of such an , Phase 1 covers all non-existing target values optimally.

Reference Implementation

C++ Solution for LeetCode

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());
        int n = nums.size();
        int ans = 1;

        // Phase 1: Generic Sliding Window (Target might not be in nums)
        // Find max window such that nums[right] - nums[left] <= 2*k
        int left = 0;
        for (int right = 0; right < n; ++right) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            // All elements in nums[left...right] can reach some common value X.
            // Since X might not be in nums, we are limited by numOperations.
            ans = max(ans, min(right - left + 1, numOperations));
        }

        // Phase 2: Specific Target Check (Target is one of nums[i])
        // We need to account for the count of the target itself to potentially exceed numOperations
        // Iterate unique elements to avoid redundant checks
        for (int i = 0; i < n;) {
            int val = nums[i];
            int count = 0;
            // Count frequency of current val
            int j = i;
            while (j < n && nums[j] == val) {
                count++;
                j++;
            }
            
            // Find range [val - k, val + k]
            // lower_bound gives first element >= val - k
            auto it_low = lower_bound(nums.begin(), nums.end(), val - k);
            // upper_bound gives first element > val + k
            auto it_high = upper_bound(nums.begin(), nums.end(), val + k);
            
            int total_in_range = distance(it_low, it_high);
            
            // We can change at most numOperations neighbors to val.
            // The total frequency is count (already val) + min(others, numOperations)
            // others = total_in_range - count
            // simplified: min(total_in_range, count + numOperations)
            ans = max(ans, min(total_in_range, count + numOperations));
            
            i = j; // Move to next unique element
        }

        return ans;
    }
};

Java Solution for LeetCode

java
import java.util.Arrays;

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 1;

        // Phase 1: Generic Sliding Window
        int left = 0;
        for (int right = 0; right < n; right++) {
            while (nums[right] - nums[left] > 2 * k) {
                left++;
            }
            ans = Math.max(ans, Math.min(right - left + 1, numOperations));
        }

        // Phase 2: Check specific targets present in nums
        // We use binary search helper functions to find ranges
        for (int i = 0; i < n;) {
            int val = nums[i];
            int count = 0;
            int j = i;
            while (j < n && nums[j] == val) {
                count++;
                j++;
            }

            // Find range [val - k, val + k]
            int lowIdx = lowerBound(nums, val - k);
            int highIdx = upperBound(nums, val + k);
            
            int totalInRange = highIdx - lowIdx;
            
            ans = Math.max(ans, Math.min(totalInRange, count + numOperations));
            
            i = j;
        }

        return ans;
    }

    // Helper: Find first index >= target
    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    // Helper: Find first index > target
    private int upperBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Python Solution for LeetCode

python
from bisect import bisect_left, bisect_right

class Solution:
    def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
        nums.sort()
        n = len(nums)
        ans = 1
        
        # Phase 1: Generic Sliding Window
        # Find max window where max(window) - min(window) <= 2*k
        left = 0
        for right in range(n):
            while nums[right] - nums[left] > 2 * k:
                left += 1
            # If target is not in nums, we are capped by numOperations
            ans = max(ans, min(right - left + 1, numOperations))
            
        # Phase 2: Specific Target Check
        # Iterate unique values to see if anchoring on an existing number is better
        i = 0
        while i < n:
            val = nums[i]
            # Count frequency of current val
            j = i
            while j < n and nums[j] == val:
                j += 1
            count = j - i
            
            # Find range [val - k, val + k]
            low_idx = bisect_left(nums, val - k)
            high_idx = bisect_right(nums, val + k)
            
            total_in_range = high_idx - low_idx
            
            # We can use existing 'count' + up to 'numOperations' converted neighbors
            ans = max(ans, min(total_in_range, count + numOperations))
            
            i = j # Move to next unique element
            
        return ans

• Mistake: Assuming the answer is always min(window_size, numOperations).
• Reasoning: If you have many duplicates of a number, say nums=[5, 5, 5] and numOperations=0, the answer is 3. The formula min(3, 0) returns 0, which is wrong.
• Consequence: Incorrect answers when the frequency of existing elements exceeds numOperations. You must include count(X) in your logic.