LeetCode Daily Problem : 2958. Length of Longest Subarray With at Most K Frequency

Problem Statement:

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example:

Input: nums = [1,2,3,1,2,3,1,2], k = 2

Output: 6

Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good. It can be shown that there are no good subarrays with length more than 6.

Photo by Bill Stephan on Unsplash

Intuition:

To find the length of the longest good subarray, we need to use a sliding window approach. We’ll maintain a hashmap num_dict to keep track of the count of elements. We'll also use l as the left pointer to track the start of the subarray and max_len to keep track of the maximum length of a good subarray.

Approach:

1. Initialize a hashmap num_dict to keep track of the count of elements, l as the left pointer to track the subarray which is good, and max_len to track the largest length of a good array.
2. Iterate through the array using r as the right pointer.
3. Increment the count of the current element in num_dict.
4. While the count of the current element exceeds k and l is less than or equal to r, decrement the count of the element at nums[l] and increment l.
5. Update max_len to be the maximum of the current max_len and the length of the current subarray (r - l + 1).
6. Return max_len as the result.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the nums array. This is because we only iterate through the array once.

Space Complexity:

The space complexity is O(n), where n is the length of the nums array. This is due to the hashmap num_dict which can store up to n distinct elements.

Code:

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:

        num_dict=defaultdict(int)
        l,max_len=0,0

        for r,num in enumerate(nums):
            num_dict[num]+=1

            while num_dict[num]>k and l<=r:
                num_dict[nums[l]]-=1
                l+=1
            
            max_len=max(max_len,r-l+1)
        
        return max_len

References :

https://www.youtube.com/watch?v=W_KYZGp2QzU&t=210s