LeetCode 3434 Maximum Frequency After Subarray Operation Solution & Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Kadane's Algorithm - The optimized solutions use Kadane's algorithm to find maximum subarray sums
Hash Maps - Used for tracking frequency counts and running sums for each value
Subarray Problems - Understanding how to enumerate and process contiguous subarrays

1. Brute Force

Intuition

The operation lets us pick a subarray and add a constant to every element in it. Our goal is to maximize how often some value k appears. The key insight is that we want to convert elements of some value num into k by choosing the right constant. For each candidate num, we try every possible subarray, count how many num values we convert to k, and subtract any k values that get changed to something else within the subarray.

Algorithm

Count how many times k appears in the array (call it cntK).
For each possible value num from 1 to 50 (excluding k):
- For each starting index i:
  - Reset the count and iterate through all ending indices j.
  - Increment count when we see num (it becomes k after the operation).
  - Decrement cntK when we see k (it changes to something else).
  - Track the maximum of cntK + count.
Return the maximum frequency found.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        n = len(nums)
        cntK = nums.count(k)
        res = cntK

        for num in range(1, 51):
            if num == k: continue
            for i in range(n):
                tmp, cnt = cntK, 0
                for j in range(i, n):
                    if nums[j] == num:
                        cnt += 1
                    elif nums[j] == k:
                        cntK -= 1
                    res = max(res, cnt + cntK)

                cntK = tmp

        return res

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        int cntK = 0;
        for (int x : nums) if (x == k) cntK++;
        int res = cntK;

        for (int num = 1; num <= 50; num++) {
            if (num == k) continue;
            for (int i = 0; i < n; i++) {
                int tmp = cntK;
                int cnt = 0;
                for (int j = i; j < n; j++) {
                    if (nums[j] == num) {
                        cnt++;
                    } else if (nums[j] == k) {
                        cntK--;
                    }
                    res = Math.max(res, cnt + cntK);
                }
                cntK = tmp;
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n = nums.size();
        int cntK = 0;
        for (int x : nums) if (x == k) cntK++;
        int res = cntK;

        for (int num = 1; num <= 50; num++) {
            if (num == k) continue;
            for (int i = 0; i < n; i++) {
                int tmp = cntK, cnt = 0;
                for (int j = i; j < n; j++) {
                    if (nums[j] == num) {
                        cnt++;
                    } else if (nums[j] == k) {
                        cntK--;
                    }
                    res = max(res, cnt + cntK);
                }
                cntK = tmp;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        const n = nums.length;
        let cntK = nums.filter((x) => x === k).length;
        let res = cntK;

        for (let num = 1; num <= 50; num++) {
            if (num === k) continue;
            for (let i = 0; i < n; i++) {
                const tmp = cntK;
                let cnt = 0;
                for (let j = i; j < n; j++) {
                    if (nums[j] === num) {
                        cnt++;
                    } else if (nums[j] === k) {
                        cntK--;
                    }
                    res = Math.max(res, cnt + cntK);
                }
                cntK = tmp;
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        int n = nums.Length;
        int cntK = 0;
        foreach (var x in nums) if (x == k) cntK++;
        int res = cntK;

        for (int num = 1; num <= 50; num++) {
            if (num == k) continue;
            for (int i = 0; i < n; i++) {
                int tmp = cntK;
                int cnt = 0;
                for (int j = i; j < n; j++) {
                    if (nums[j] == num) {
                        cnt++;
                    } else if (nums[j] == k) {
                        cntK--;
                    }
                    res = Math.Max(res, cnt + cntK);
                }
                cntK = tmp;
            }
        }
        return res;
    }
}

func maxFrequency(nums []int, k int) int {
    n := len(nums)
    cntK := 0
    for _, x := range nums {
        if x == k {
            cntK++
        }
    }
    res := cntK

    for num := 1; num <= 50; num++ {
        if num == k {
            continue
        }
        for i := 0; i < n; i++ {
            tmp := cntK
            cnt := 0
            for j := i; j < n; j++ {
                if nums[j] == num {
                    cnt++
                } else if nums[j] == k {
                    cntK--
                }
                if cnt+cntK > res {
                    res = cnt + cntK
                }
            }
            cntK = tmp
        }
    }
    return res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        val n = nums.size
        var cntK = nums.count { it == k }
        var res = cntK

        for (num in 1..50) {
            if (num == k) continue
            for (i in 0 until n) {
                val tmp = cntK
                var cnt = 0
                for (j in i until n) {
                    if (nums[j] == num) {
                        cnt++
                    } else if (nums[j] == k) {
                        cntK--
                    }
                    res = maxOf(res, cnt + cntK)
                }
                cntK = tmp
            }
        }
        return res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let n = nums.count
        var cntK = nums.filter { $0 == k }.count
        var res = cntK

        for num in 1...50 {
            if num == k { continue }
            for i in 0..<n {
                let tmp = cntK
                var cnt = 0
                for j in i..<n {
                    if nums[j] == num {
                        cnt += 1
                    } else if nums[j] == k {
                        cntK -= 1
                    }
                    res = max(res, cnt + cntK)
                }
                cntK = tmp
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut cnt_k = nums.iter().filter(|&&x| x == k).count() as i32;
        let mut res = cnt_k;

        for num in 1..=50 {
            if num == k {
                continue;
            }
            for i in 0..n {
                let tmp = cnt_k;
                let mut cnt = 0;
                for j in i..n {
                    if nums[j] == num {
                        cnt += 1;
                    } else if nums[j] == k {
                        cnt_k -= 1;
                    }
                    res = res.max(cnt + cnt_k);
                }
                cnt_k = tmp;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(50 * n ^ 2)$
Space complexity: $O(1)$

2. Kadane's Algorithm - I

Intuition

The brute force tries all subarrays, but we can use Kadane's algorithm to find the best subarray in linear time. For a fixed target value num, we want to find a subarray where converting num to k gives the maximum net gain. Treat each num as +1 (we gain a k) and each k as -1 (we lose a k). Kadane's algorithm finds the maximum sum subarray, giving us the best gain for that target.

Algorithm

Count how many times k appears in the array (call it cntK).
For each possible value i from 1 to 50 (excluding k):
- Initialize cnt = 0.
- For each element in the array:
  - Add 1 if the element equals i.
  - Subtract 1 if the element equals k.
  - Reset cnt to 0 if it goes negative (Kadane's reset).
  - Track the maximum of cntK + cnt.
Return the maximum frequency found.

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        cntK = nums.count(k)
        res = 0

        for i in range(1, 51):
            if i == k:
                continue
            cnt = 0
            for num in nums:
                if num == i:
                    cnt += 1
                if num == k:
                    cnt -= 1
                cnt = max(cnt, 0)
                res = max(res, cntK + cnt)
        return res

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        int cntK = 0;
        for (int num : nums) {
            if (num == k) cntK++;
        }
        int res = 0;

        for (int i = 1; i <= 50; i++) {
            if (i == k) continue;
            int cnt = 0;
            for (int num : nums) {
                if (num == i) cnt++;
                if (num == k) cnt--;
                cnt = Math.max(cnt, 0);
                res = Math.max(res, cntK + cnt);
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int cntK = 0;
        for (int num : nums) {
            if (num == k) cntK++;
        }
        int res = 0;

        for (int i = 1; i <= 50; i++) {
            if (i == k) continue;
            int cnt = 0;
            for (int num : nums) {
                if (num == i) cnt++;
                if (num == k) cnt--;
                cnt = max(cnt, 0);
                res = max(res, cntK + cnt);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        let cntK = 0;
        for (const num of nums) {
            if (num === k) cntK++;
        }
        let res = 0;

        for (let i = 1; i <= 50; i++) {
            if (i === k) continue;
            let cnt = 0;
            for (const num of nums) {
                if (num === i) cnt++;
                if (num === k) cnt--;
                cnt = Math.max(cnt, 0);
                res = Math.max(res, cntK + cnt);
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        int cntK = 0;
        foreach (var num in nums) {
            if (num == k) cntK++;
        }
        int res = 0;

        for (int i = 1; i <= 50; i++) {
            if (i == k) continue;
            int cnt = 0;
            foreach (var num in nums) {
                if (num == i) cnt++;
                if (num == k) cnt--;
                cnt = Math.Max(cnt, 0);
                res = Math.Max(res, cntK + cnt);
            }
        }
        return res;
    }
}

func maxFrequency(nums []int, k int) int {
    cntK := 0
    for _, num := range nums {
        if num == k {
            cntK++
        }
    }
    res := 0

    for i := 1; i <= 50; i++ {
        if i == k {
            continue
        }
        cnt := 0
        for _, num := range nums {
            if num == i {
                cnt++
            }
            if num == k {
                cnt--
            }
            if cnt < 0 {
                cnt = 0
            }
            if cntK+cnt > res {
                res = cntK + cnt
            }
        }
    }
    return res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        val cntK = nums.count { it == k }
        var res = 0

        for (i in 1..50) {
            if (i == k) continue
            var cnt = 0
            for (num in nums) {
                if (num == i) cnt++
                if (num == k) cnt--
                cnt = maxOf(cnt, 0)
                res = maxOf(res, cntK + cnt)
            }
        }
        return res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        let cntK = nums.filter { $0 == k }.count
        var res = 0

        for i in 1...50 {
            if i == k { continue }
            var cnt = 0
            for num in nums {
                if num == i { cnt += 1 }
                if num == k { cnt -= 1 }
                cnt = max(cnt, 0)
                res = max(res, cntK + cnt)
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 {
        let cnt_k = nums.iter().filter(|&&x| x == k).count() as i32;
        let mut res = 0;

        for i in 1..=50 {
            if i == k {
                continue;
            }
            let mut cnt = 0;
            for &num in &nums {
                if num == i {
                    cnt += 1;
                }
                if num == k {
                    cnt -= 1;
                }
                cnt = cnt.max(0);
                res = res.max(cnt_k + cnt);
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(50 * n)$
Space complexity: $O(1)$

3. Kadane's Algorithm - II

Intuition

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.

Algorithm

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

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

public class Solution {
    public int maxFrequency(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int res = 0;
        for (int num : nums) {
            int prev = Math.max(cnt.getOrDefault(num, 0), cnt.getOrDefault(k, 0));
            cnt.put(num, prev + 1);
            res = Math.max(res, cnt.get(num) - cnt.getOrDefault(k, 0));
        }
        return cnt.getOrDefault(k, 0) + 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;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxFrequency(nums, k) {
        const cnt = new Map();
        let res = 0;
        for (const num of nums) {
            const prev = Math.max(cnt.get(num) || 0, cnt.get(k) || 0);
            cnt.set(num, prev + 1);
            res = Math.max(res, cnt.get(num) - (cnt.get(k) || 0));
        }
        return (cnt.get(k) || 0) + res;
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k) {
        var cnt = new Dictionary<int,int>();
        int res = 0;
        foreach (var num in nums) {
            int prev = Math.Max(
                cnt.TryGetValue(num, out var cn) ? cn : 0,
                cnt.TryGetValue(k, out var ck) ? ck : 0
            );
            cnt[num] = prev + 1;
            res = Math.Max(res, cnt[num] - (cnt.TryGetValue(k, out ck) ? ck : 0));
        }
        return (cnt.TryGetValue(k, out var ckk) ? ckk : 0) + res;
    }
}

func maxFrequency(nums []int, k int) int {
    cnt := make(map[int]int)
    res := 0
    for _, num := range nums {
        prev := cnt[num]
        if cnt[k] > prev {
            prev = cnt[k]
        }
        cnt[num] = prev + 1
        if cnt[num]-cnt[k] > res {
            res = cnt[num] - cnt[k]
        }
    }
    return cnt[k] + res
}

class Solution {
    fun maxFrequency(nums: IntArray, k: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        var res = 0
        for (num in nums) {
            val prev = maxOf(cnt.getOrDefault(num, 0), cnt.getOrDefault(k, 0))
            cnt[num] = prev + 1
            res = maxOf(res, cnt[num]!! - cnt.getOrDefault(k, 0))
        }
        return cnt.getOrDefault(k, 0) + res
    }
}

class Solution {
    func maxFrequency(_ nums: [Int], _ k: Int) -> Int {
        var cnt = [Int: Int]()
        var res = 0
        for num in nums {
            let prev = max(cnt[num, default: 0], cnt[k, default: 0])
            cnt[num] = prev + 1
            res = max(res, cnt[num]! - cnt[k, default: 0])
        }
        return cnt[k, default: 0] + res
    }
}

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 {
        let mut cnt = HashMap::new();
        let mut res = 0;
        for &num in &nums {
            let prev = *cnt.get(&num).unwrap_or(&0).max(cnt.get(&k).unwrap_or(&0));
            *cnt.entry(num).or_insert(0) = prev + 1;
            res = res.max(cnt[&num] - cnt.get(&k).unwrap_or(&0));
        }
        *cnt.get(&k).unwrap_or(&0) + res
    }
}

Time & Space Complexity

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

Common Pitfalls

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.