< Back





2958. Length of Longest Subarray With at Most K Frequency

This is somewhat related to 3. Longest Substring Without Repeating Characters,
however, we are now looking for the longest subarray with at most k frequency of any number.

Just like our related problem, we maintain a hashmap to keep track of the numbers we've seen, but
this time we take action to shrink the window when the frequency of a number is greater than k.
Instead of the left pointer jumping to the last seen location of the number in question, we have to
gradually shrink the array because the number in question has been seen multiple times.

So to solve this, while the left pointer is less than the right pointer and the number in question is
still larger than k, we decrement the frequency of the number pointed to by the left pointer and
increment the left pointer. Eventually, the number in question will no longer have a frequency
greater than k.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def maxSubarrayLength(self, nums: List[int], k: int) -> int:
          count = defaultdict(int)
          ans = l = 0

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

              if count[num] > k:
                  while l < r and count[num] > k:
                      count[nums[l]] -= 1
                      l += 1

              ans = max(ans, r - l + 1)

          return ans


_ Time Complexity:

  O(n) - We have to iterate through the entire input array.

_ Space Complexity:

  O(n) - We store the frequency of each number in the input array.