Problem of The Day: Length of Longest Subarray With at Most K Frequency

Problem Statement

Intuition

Initially, I’m considering using a sliding window approach to solve this problem. By maintaining a window and adjusting it based on certain conditions, I should be able to efficiently find the maximum subarray length where the frequency of each element is at most k.

Approach

I’ll initialize pointers start and end to mark the beginning and end of the current window, respectively. I’ll also use a dictionary (freq) to keep track of the frequency of each element within the current window. The idea is to move the end pointer forward, updating the frequency dictionary accordingly. If the frequency of any element exceeds k, I’ll adjust the start pointer to shrink the window until the condition is met again. At each step, I’ll update the result with the maximum subarray length found so far.

Complexity

• Time complexity: O(n), where n is the length of the input list nums. The algorithm scans through the list once.

• Space complexity: O(n), where n is the length of the input list nums. The space complexity is due to the dictionary freq, which could potentially store all elements of the list.

Code

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        start = end = 0
        freq = defaultdict(int)
        res = 0
        for end, num in enumerate(nums):
            freq[num] += 1
            while start <= end and freq[num] > k:
                freq[nums[start]] -= 1
                start += 1
            res = max(res, end - start + 1)

        return res