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 After Subarray Operation

Number: 3751

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array nums and an integer k, you are allowed to perform one operation: select any contiguous subarray and add a chosen integer x to every element in that subarray. After this operation, some elements in the array may become equal to k. The goal is to choose the optimal subarray and integer x so that the frequency (i.e. the count) of k in the final array is maximized. Return this maximum frequency.

Key Insights

  • The operation affects a contiguous subarray; every index in that range gets increased by the same integer x.
  • For any index in the subarray to become k after adding x, it must be that nums[i] + x = k, i.e. x = k - nums[i]. This forces that only those indices with a particular value (say v) in the chosen subarray will “convert” to k when we set x = k - v.
  • If the chosen subarray (with x = k - v) contains any index that was originally k (and v ≠ k) then that index becomes k + (k - v) ≠ k, effectively “losing” a k that was already present.
  • Therefore, one must decide between leaving already k’s untouched and converting as many non-k values as possible. For a candidate value v (where v may not be equal to k), if we choose x = k - v then within the chosen subarray each element that equals v becomes k while each element that was originally k becomes non-k.
  • The overall final count will be: • the count of indices originally equal to k that are left outside the subarray (and thus remain k) plus • the count of indices inside the subarray that were equal to v (and now become k).
  • Equivalently, if base is the total frequency of k in the array (all indices initially k), and if we let S be the chosen contiguous subarray, then the net change in frequency is: gain = (# indices in S with value v) – (# indices in S with value k).
  • For each candidate v (v from 1 to 50, including v = k – though v = k corresponds to x = 0 and does not change the frequency), the problem reduces to finding a contiguous subarray that maximizes (count_v – count_k).
  • This can be solved by transforming the array into a “difference array” for each candidate v and then using the Kadane algorithm to get the maximum subarray sum.
  • The answer is then base + max(0, maximum gain over all candidates).

Space and Time Complexity

Time Complexity: O(50 * n) = O(n), since we iterate through the array for each candidate value. Space Complexity: O(1) extra space (besides the input), as we use only counters and temporary variables for the Kadane algorithm.

Solution

The algorithm works as follows:

  1. Compute the base frequency of k in the entire array.
  2. For each candidate value v in the range [1, 50] (v may be equal to k, but note that x would be 0 then and no improvement is possible), create a temporary transformed array where each element is:
    • +1 if the element equals v (indicating that if we choose x = k - v this element will “convert” to k)
    • -1 if the element equals k (because if we include an element originally k in the subarray, it will lose its k value)
    • 0 otherwise.
  3. Use Kadane’s algorithm on this transformed array to find the maximum subarray sum. This maximum sum represents the best net gain (number of newly added k’s minus lost ones) that can be achieved for that candidate v when applying the subarray operation.
  4. Take the maximum gain across all candidate values (if the gain is negative, ignore it as it is better not to use the operation in that case).
  5. The final answer is the base count plus the best gain.

Key details/tricks:

  • Although the subarray can contain elements that don’t contribute positively (i.e. neither equal to v nor k), they contribute 0 and do not affect the running sum.
  • We must avoid “spoiling” already k positions if they do not help the overall count for a candidate v ≠ k.
  • When v equals k (x = 0), the operation is essentially a no-op so it is only as good as leaving the array unchanged.

This approach efficiently searches over all possible transformations and subarrays with a single pass per candidate.

Code Solutions

# Python solution using Kadane's algorithm for each candidate value.
def maxFrequencyAfterSubarrayOperation(nums, k):
    # Count the total occurrences of k in the original array.
    base = sum(1 for num in nums if num == k)
    best_gain = 0  # Best additional frequency we can gain from a subarray operation.

    # Loop over candidate values. These are the values we want to convert to k.
    for v in range(1, 51):
        # For candidate v, x should be k - v.
        # When applying the operation with x = k - v, only positions with value v will become k.
        # Also, any index originally equal to k included in the subarray will become k + (k - v) != k if v != k.
        # So we assign +1 for a v (gain) and -1 for a k (loss).
        current_gain = 0
        max_gain_for_v = 0
        for num in nums:
            # Determine contribution for current num
            if num == v:
                current_gain += 1  # It would convert to k.
            elif num == k:
                current_gain -= 1  # It is already k, inclusion means losing a k.
            
            # Reset if negative
            if current_gain < 0:
                current_gain = 0
            # Update maximum gain found so far for candidate v.
            if current_gain > max_gain_for_v:
                max_gain_for_v = current_gain
        
        # Update best overall gain.
        if max_gain_for_v > best_gain:
            best_gain = max_gain_for_v

    # Final answer is the original count of k plus the best additional gain.
    return base + best_gain

# Example usage:
print(maxFrequencyAfterSubarrayOperation([1,2,3,4,5,6], 1))  # Expected output: 2
print(maxFrequencyAfterSubarrayOperation([10,2,3,4,5,5,4,3,2,2], 10))  # Expected output: 4
← Back to All Questions