LeetCode 2958 solution

problem

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.

python

from typing import List
from collections import Counter

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        left = 0
        max_length = 0
        freq = Counter()

        for right in range(len(nums)):
            freq[nums[right]] += 1
            
            while freq[nums[right]] > k:
                freq[nums[left]] -= 1
                left += 1
            
            max_length = max(max_length, right - left + 1)
        
        return max_length

슬라이딩 윈도우 알고리즘 사용

슬라이딩 윈도우 기법을 사용하면 배열을 한 번만 순회하면서 문제를 해결할 수 있습니다. 이 방식에서는 "윈도우"라고 하는 배열의 연속된 부분을 고려합니다. 이 윈도우는 배열의 한 쪽 끝에서 시작하여 다른 쪽 끝으로 이동하며, 윈도우의 크기는 동적으로 변할 수 있습니다.

1. 윈도우 초기화: 윈도우의 왼쪽과 오른쪽 끝을 배열의 시작 부분에 위치시킵니다.
2. 윈도우 확장: 윈도우의 오른쪽 끝을 점차적으로 확장하면서 각 숫자의 빈도수를 기록합니다.
3. 조건 검사: 어떤 숫자의 빈도수가 K를 초과하면 윈도우의 왼쪽을 오른쪽으로 이동시켜 윈도우 크기를 조정합니다. 이 때, 왼쪽에 있던 숫자의 빈도수를 감소시킵니다.
4. 최대 길이 갱신: 위의 조건을 만족하면서 윈도우를 확장할 때마다 윈도우의 크기(길이)를 확인하고, 이를 최대 길이와 비교하여 필요하다면 업데이트합니다.