Maximum Frequency After Subarray Operation

How it works

We can process all target values simultaneously in a single pass. For each number, we track the best running sum ending at the current position. When we see a number, its count can either extend from its previous best or start fresh from k's position (since we could start our subarray here). The maximum difference between any count and k's count represents the best gain achievable.

Steps

1. Maintain a hash map cnt where cnt[num] represents the best running sum ending at the current position for converting num to k.
2. For each element in the array:
   • Update cnt[num] = max(cnt[num], cnt[k]) + 1.
   • Track the maximum value of cnt[num] - cnt[k].
3. Return cnt[k] + res, where res is the maximum gain found.

Complexity

• Time complexity: O(n)
• Space complexity: O(50)

Things to watch for

Misunderstanding the Subarray Operation

The operation adds a constant to every element in a chosen subarray. A common mistake is to think you can selectively modify some elements within the subarray while leaving others unchanged. Every element in the range [l, r] gets the same constant added. This means if you have both k and num values in your chosen subarray, converting num to k will simultaneously change existing k values to something else.

Forgetting to Account for Lost k Values

When you apply the operation to a subarray to convert num values to k, any existing k values within that subarray become k + constant, which is no longer k. The net gain is (count of num in subarray) - (count of k in subarray). Solutions that only count the gains without subtracting the losses will produce incorrect results.

Not Resetting State Between Target Values

When iterating through all possible target values (1 to 50), each target requires its own independent Kadane's algorithm pass. Failing to reset the running count between targets will carry over state from previous iterations, leading to incorrect maximum subarray calculations. Initialize cnt = 0 at the start of each target value's iteration.

Ignoring the No-Operation Case

The operation is optional. Sometimes the best strategy is to not perform any operation at all, especially when k already appears frequently. The answer should always be at least count(k) in the original array. Some solutions focus so heavily on finding the best subarray that they forget to compare against the base case of leaving the array unchanged.

Applying the Wrong Kadane's Variant

Kadane's algorithm finds the maximum sum subarray, but the classic version requires at least one element. In this problem, an empty subarray (doing nothing to convert any num to k) is valid and contributes 0 to the gain. Solutions must allow the running sum to reset to 0 when it goes negative, representing the choice to not include those elements in the operation subarray.

from typing import List
from collections import defaultdict

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        res = 0
        for num in nums:
            cnt[num] = max(cnt[num], cnt[k]) + 1
            res = max(res, cnt[num] - cnt[k])
        return cnt[k] + res

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        int res = 0;
        for (int num : nums) {
            int prev = max(cnt[num], cnt[k]);
            cnt[num] = prev + 1;
            res = max(res, cnt[num] - cnt[k]);
        }
        return cnt[k] + res;
    }
};