We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Frequency of an Element After Performing Operations II

Number: 3640

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer array nums and two integers k and numOperations, you must perform exactly numOperations “operations” on distinct indices of nums. In each operation you can add any integer from -k to k to the chosen element. The goal is to maximize the frequency (the count of occurrences) of some element (target value) in nums after these operations. An element which is already equal to the target does not need to be changed, but if an element is not equal to the target it can be changed in one operation provided that the difference |nums[i] – target| is at most k. Return the maximum possible frequency of any element after performing the operations.

Key Insights

  • An index can be modified at most once by adding a value from the range [-k, k].
  • For any chosen target value T, an element x can become T if |x – T| ≤ k.
  • If an element is already equal to T, no operation is needed.
  • For a candidate target T: • Let freeCount = frequency of T already in nums. • Let eligibleCount = the total number of elements x with x in [T – k, T + k] (since these can be “converted” to T in one operation).
  • The maximum frequency obtainable for target T is freeCount + min(numOperations, eligibleCount – freeCount).
  • Also note that sometimes a target value not present in the array may yield a better result; in that case, all elements in the chosen “window” would require an operation and the maximum frequency is limited by numOperations (and by the size of that eligible window).
  • Using sorting and binary search (or a sliding window) helps count how many elements lie in any interval [T – k, T + k].
  • The eligible set for any candidate T is all array elements in an interval of fixed length (2*k + 1). This fact can be used in a sliding window over the sorted array.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search for each candidate unique number. Space Complexity: O(n) for storing the sorted array and frequency map.

Solution

We first sort the array and build a frequency map of the numbers. For each candidate target T that appears in the array, we use binary search on the sorted array to count the number of elements in the range [T – k, T + k]. The maximum frequency we can achieve with target T is the sum of freeCount (the number of elements already equal to T) and the minimum of numOperations and the number of eligible elements that are not T (i.e. eligibleCount – freeCount), so it is given by min(freeCount + numOperations, eligibleCount).

We also consider targets T that are not in the array. In that case the frequency equals the number of elements we can “convert” to T, but each conversion costs one operation and only elements within T ± k qualify. This reduces to a sliding window problem over the sorted array in which we find the maximum count of numbers whose difference is at most 2*k. The best possible frequency in that scenario will be min(maxWindowCount, numOperations).

The final answer is the maximum among these candidate frequencies.

Code Solutions

# Python solution with detailed comments
import bisect
from collections import Counter

def maxFrequency(nums, k, numOperations):
    # First sort the array for efficient window computation
    nums.sort()
    
    # Frequency map for numbers in the array
    freq = Counter(nums)
    
    n = len(nums)
    best = 0
    
    # For each candidate target that appears in nums, use binary search to find the eligible count.
    for target in freq:
        freeCount = freq[target]
        # Find lower bound for (target - k) and upper bound for (target + k)
        left_index = bisect.bisect_left(nums, target - k)
        right_index = bisect.bisect_right(nums, target + k)
        eligibleCount = right_index - left_index
        # The maximum frequency achievable with target T
        best = max(best, min(freeCount + numOperations, eligibleCount))
    
    # Consider the case when target is not in the array.
    # For these targets free count is 0, so the frequency is limited to converting eligible numbers.
    # We can compute the maximum number of numbers that lie in any window of length 2*k,
    # meaning that they are all within T ± k for some optimal T.
    maxWindow = 0
    left = 0
    for right in range(n):
        # Expand the window until the difference is larger than 2*k
        while nums[right] - nums[left] > 2 * k:
            left += 1
        maxWindow = max(maxWindow, right - left + 1)
    # For a target not in the array, the frequency is min(numOperations, window count)
    best = max(best, min(maxWindow, numOperations))
    
    return best

# Example usage:
print(maxFrequency([1,4,5], 1, 2))  # Expected output: 2
print(maxFrequency([5,11,20,20], 5, 1))  # Expected output: 2
← Back to All Questions