2958. Length of Longest Subarray With at Most K Frequency
This is a very common subarray technique, remember since it’s a subarray it has to be a sliding window. If it were a , it becomes a DP or greedy solution.
We just keep track of current elements and their increasing/decreasing frequencies in a dict/table. At every iteration, if the frequency of the current element ($freq[nums[right]]$)
goes beyond k, we start shrinking the window from the left.
Code:
Python
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
res = 0
freq = dict()
left = 0
for right, n in enumerate(nums):
if n in freq.keys():
freq[n] += 1
if freq[n] > k:
while freq[nums[right]] > k:
freq[nums[left]] -= 1
left += 1
else:
freq[n] = 1
res = max(right - left + 1, res)
return res
Big O Analysis
- Runtime The runtime here is since we are visiting each element once.
- Memory We use a frequency table so the memory order is
— A