Problem Description
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.
Key Insights
- A "good" subarray has each element occurring at most k times.
- We can utilize the sliding window technique to efficiently find the longest good subarray.
- A hash table (or dictionary) can be used to keep track of the frequencies of elements within the current window.
- When the frequency of any element exceeds k, we need to shrink the window from the left.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the nums array. Each element is processed at most twice (once added and once removed). Space Complexity: O(m), where m is the number of unique elements in the current window, which can be at most n in the worst case.
Solution
We will use a sliding window approach with two pointers (left and right). The right pointer will expand the window by adding elements, while the left pointer will shrink the window when the frequency of any element exceeds k. A hash table will be employed to keep track of the frequency of elements in the current window.