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 I

Number: 3622

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array nums and two integers k and numOperations, you are allowed to perform exactly numOperations operations. In each operation, you select an index that has not been used before and add any integer from the range [-k, k] to nums[i]. The goal is to maximize the frequency (the count) of any element in nums after these operations.

Key Insights

  • Each operation can adjust one element by at most k in either direction.
  • An element already equal to the target value does not need an operation.
  • For a candidate target value T, only those numbers that are already T or can be changed to T (i.e. those satisfying |nums[i] - T| ≤ k) are eligible.
  • The maximum achievable frequency for T is: frequency(T) plus at most numOperations additional eligible numbers (i.e. those within [T - k, T + k] that are not already T).
  • Using a frequency array and prefix sum over the value range allows computing the count of numbers in any interval quickly.
  • Finally, iterate over candidate target values in the range of possible numbers to find the maximum achievable frequency.

Space and Time Complexity

Time Complexity: O(M) where M is the maximum possible value (up to 10^5), since we precompute frequency and prefix sums and then iterate over the candidate values. Space Complexity: O(M) for the frequency and prefix sum arrays.

Solution

We first count the frequency of every possible value in nums. Then, using a prefix sum array over this frequency array, we can quickly determine the number of elements whose values lie in any interval [T-k, T+k]. For each candidate target T (from 1 to maximum value), the eligible count is the number of elements in the range [T-k, T+k].

Since any element that is not already T but lies in this interval can be changed into T by using one operation (provided we have not exceeded numOperations), the maximum achievable frequency if we pick T as the target is:

  frequency(T) + min(numOperations, (eligible count − frequency(T)))

We take the maximum value across all possible T. This approach uses frequency arrays, prefix sum techniques, and a linear scan over possible target values.

Code Solutions

# Python Solution

def maxFrequency(nums, k, numOperations):
    # Find the maximum number in nums to size the frequency array
    max_val = max(nums)
    freq = [0] * (max_val + 2)  # 1-indexed; extra space for prefix sum convenience

    # Build frequency array: count occurrence of each number
    for num in nums:
        freq[num] += 1

    # Build prefix sum array for frequencies
    prefix = [0] * (max_val + 2)
    for i in range(1, max_val + 1):
        prefix[i] = prefix[i - 1] + freq[i]

    max_frequency = 0
    # Iterate candidate T from 1 to max_val
    for T in range(1, max_val + 1):
        # Determine the boundaries for eligible values: [T-k, T+k]
        lower = max(1, T - k)
        upper = min(max_val, T + k)
        # Count of eligible elements in the interval
        eligible_count = prefix[upper] - prefix[lower - 1]
        current_frequency = freq[T] + min(numOperations, eligible_count - freq[T])
        max_frequency = max(max_frequency, current_frequency)
    
    return max_frequency

# 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