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 1:
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.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.
Example 3:
Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length
The most straightforward approach is to generate all possible subarrays and check if each one is "good" (i.e., the frequency of each element is less than or equal to k
).
k
, the subarray is not good.Code (Python):
def longest_good_subarray_brute_force(nums, k):
max_len = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
subarray = nums[i:j+1]
counts = {}
is_good = True
for num in subarray:
counts[num] = counts.get(num, 0) + 1
if counts[num] > k:
is_good = False
break
if is_good:
max_len = max(max_len, len(subarray))
return max_len
Time Complexity: O(n3). Generating all subarrays takes O(n2) time, and checking each subarray takes O(n) time.
Space Complexity: O(n). In the worst case, we might store all n
elements of the input array in the counts
dictionary.
We can use a sliding window approach to solve this problem more efficiently. The idea is to maintain a window and expand it to the right as long as the subarray within the window is "good". If the subarray becomes "bad" (i.e., an element's frequency exceeds k
), we shrink the window from the left until it becomes "good" again.
k
, shrink the window from the left until all frequencies are within the limit.Code (Python):
def longest_good_subarray(nums, k):
max_len = 0
left = 0
counts = {}
for right in range(len(nums)):
counts[nums[right]] = counts.get(nums[right], 0) + 1
while counts[nums[right]] > k:
counts[nums[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Time Complexity: O(n). Each element is visited at most twice (once by the right pointer and once by the left pointer).
Space Complexity: O(n). In the worst case, the counts
dictionary might store the frequency of all n
elements if they are distinct.
k
is 0, then no element can appear more than 0 times. Thus, the longest "good" array can only consist of unique elements if the first element of the array is kept; every other element must be removed from the array. However, according to the problem constraints, k >= 1, so this case is not possible.k
is greater than or equal to the length of the array, the entire array is a good subarray.k
.