July 4, 2025 - Leetcode drill¶

🎯 Daily Goals¶

Review Anki Deck
Lumosity Training
Leetcode problem

📝 What I Learned¶

3434.Maximum Frequency After Subarray Operation

Topics: Array, Greedy, Dynamic Programming, Prefix Sum¶

📝 Thinking Process:¶

The naive solution would be iterating through all of the possible enumeration of i, j and count the maximum frequency of a particular element within the subarray and then add it to the counts of k before and after the subarray. It would take O(n³) time if we don't do any optimization. For optimization we can do a prefix sum to store the frequencies, making it possible to achieve O(1) for frequency range query. Even with optimization the time complexity is still O(n²) which is obviously not good enough. One of the common mindset I would love to use when dealing with array is to think of if we know the solution to part of the array how would that help us if a new element is added to that array. (Which is essentially DP) From the prompt, we can see some resemblence to the maximum subarray problem which reduces the O(n²) brute force solution to O(n) using Kadane Algorithm

Kadane Algorithm

Kadane Algorihtm is basically saying one thing: let's iterate through each element of the array and find the maximum subarray that ends with each one of them. The beautiful thing is that if we know the maximum subarray of the previous element, the maximum subarray sum of the current element would either be the sum of this element itself or the element appended to the previous maximum subarray.

Here it is slightly trickier than the original Kadane Algorithm. Instead of finding the maximum ending sum of each element, we needs to find the maximum frequency of k if the subarray ends with an element. Since we can mutate any element in the subarray, we might as well fix the mutated element to a particular one to simplify it. (This makes sense since the value range of each element is [1, 50]) After, we fixed the mutated element and calculated the maximum fequency of previous subarray, we can infer the one for the current element.

There are two cases:

if the current element is the mutated element. The maximum frequency would always be the previous one + 1
if the current element is something else. We would need to check between the result of appending the current element to the previous subarray or using itself as a new subarray.

Here is my initial attempt at the question:

class Solution:
    def getPreCounts(self, prefix_counts, i):
        return prefix_counts[i]

    def getPostCounts(self, prefix_counts, j):
        return prefix_counts[-1] - prefix_counts[j + 1]

    def maxFixedFrequency(self, nums, prefix_counts, d, k):
        cur_freq = max_freq = 0
        for j in range(len(nums)):
            post_counts = self.getPostCounts(prefix_counts, j)
            if nums[j] == d:
                cur_freq = max(cur_freq + 1, 1 + self.getPreCounts(prefix_counts, j))
            else:
                cur_freq = max(cur_freq, self.getPreCounts(prefix_counts, j))
            max_freq = max(max_freq, cur_freq + post_counts)
        return max_freq

    def maxFrequency(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        max_freq = 0
        prefix_counts = [0 for _ in range(len(nums) + 1)]
        for i in range(len(nums)):
            prefix_counts[i + 1] = prefix_counts[i]
            if nums[i] == k:
                prefix_counts[i + 1] += 1
        # fix the mutating element
        for d in range(1, 51):
            if d == k:
                max_freq = max(max_freq, prefix_counts[-1])
                continue
            max_freq = max(max_freq, self.maxFixedFrequency(nums, prefix_counts, d, k))
        return max_freq

🚀Leetcode and Problem Solving takeaways:¶

Using DP mindset to improve time complexity
When you see ranges or subarrays, prefix sum would help you perform faster queries
Always add new functions for better code readability and modularity. It can also help you think faster. (Think of the function as a black box to speed up your thinking process)

🤦‍♂️Hiccups during Implementation:¶

prefix sum requires n + 1 element to properly represent all range queries. The ith element of the prefix sum means the sum of all element up to i - 1 in the original array
Subarray is always non empty
Understanding of maximum in Kadane Algorithm. Think of why the maximum subarray sum of that ends with the current element would either be the sum of this element itself or the element appended to the previous maximum subarray.
Breaking the problem into easier ones. (Fixing the mutating element. Assuming we know the prefix maximum frequency)
Classification. What happens when the current element is k? What if it is the mutated element d? What if d and k is the same?