3434.Maximum_Frequency_After_Subarray_Operation(Medium).md

3434. Maximum Frequency After Subarray Operation (Medium)

Link: https://leetcode.com/problems/maximum-frequency-after-subarray-operation

Date	Stopwatch	Y/N	Feedback
Jun 17, 2025

Walk-through:

Intuitively, we want to know how many k already exist in nums, so we can first count how many k we have so far, then find the most k we can make from nums.

1. Loop over nums to find the total of existed k.

2. Use global variable ans to save the most extra k we can make from nums. Since the constraint is 1 <= nums[i] <= 50, so we can try each val from [1, 50] and see which val exists the most in nums. And we can use Kadane's algorithm to find the most counted val by checking each num in nums, if val == num, increment the count, if val == k, decrement the count because it will not be k after operation.
   We update cnt_freq, cnt_max each time when we are looping nums, because by Kadane's algorithm, if cnt_freq < 0, means we should skip this current subarray of nums, we keep cnt_freq = max(cnt_freq, 0), if it leads to negative, we rather don't take this subarray. We update cnt_max at the same time, if current cnt_freq leads to higher count. However, we only update ans after we finish looping nums, if cnt_max > ans we know there is a subarray from nums with current val can apply operation to get more k.

3. Return ans + k_cnt, the number of existed k in nums + how many elements we can apply operation to lead to the max frequency of k.

Python:

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        # 1. Count how many k we have in nums
        # 2. Since we want to find the mode in nums, brute force to try val from [1, 50], if num in nums == val, increment cnt, if num == k, decrement cnt, because k will not be k after increment of val
        # TC: O(n), n=len(nums), SC: O(1)

        # Count how many k in nums
        k_cnt = 0
        for num in nums:
            if num == k:
                k_cnt += 1
        ans = 0
        # Try val from[1, 50]
        for val in range(1, 51):
            # Count how many num in nums == val
            if val == k:
                continue
            cnt_freq, cnt_max = 0, 0
            # Loop over nums
            for num in nums:
                if num == val:
                    cnt_freq += 1
                elif num == k:
                    cnt_freq -= 1
                # Kadane's algorithm, if this leads to negative, rather just don't take them
                cnt_freq = max(cnt_freq, 0)
                cnt_max = max(cnt_max, cnt_freq)
            ans = max(ans, cnt_max)
        return ans + k_cnt

Time Complexity: $O(n)$
Space Complexity: $O(1)$

C++:

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        /* 
        1. Count existed k in nums
        2. Loop over [1, 50], choose the one with most frequent in nums
        3. Return k_cnt + most_cnt
        TC: O(n), SC: O(1)
        */

        int k_cnt = 0, max_cnt = 0;
        // Count total existed k in nums
        for (int num: nums) {
            if (num == k) {
                k_cnt++;
            }
        }
        // Loop over [1, 50]
        for (int i = 0; i < 51; i++) {
            // Skip if i == k
            if (i == k) {
                continue;
            }
            // Count the most frequent subarray of i in nums
            int cnt_freq = 0, cnt_max = 0;
            for (int num: nums) {
                if (num == i) {
                    cnt_freq++;
                } else if (num == k) {
                    cnt_freq--;
                }
                // Kadane's algorithm, if cnt_freq < 0, rather don't take subarray
                cnt_freq = std::max(cnt_freq, 0);
                cnt_max = std::max(cnt_freq, cnt_max);
            }
            // After current i, we will find the most frequent subarray of i
            max_cnt = std::max(max_cnt, cnt_max);
        }
        return k_cnt + max_cnt;
    }
};