Problem Description

You are given an integer array nums and an integer k.

The frequency of an element is defined as the number of times that element appears in an array.

An array is considered good if every element in the array appears at most k times (i.e., the frequency of each element is less than or equal to k).

Your task is to find the length of the longest good subarray in nums.

A subarray is a contiguous sequence of elements from the array that must be non-empty.

For example:

• If nums = [1, 2, 1, 2, 3] and k = 2, the entire array is good because each element appears at most 2 times, so the answer would be 5.
• If nums = [1, 1, 1, 2] and k = 2, the longest good subarray would be [1, 1, 2] with length 3, since including all three 1's would violate the frequency constraint.

The solution uses a sliding window approach with two pointers. The right pointer i expands the window by iterating through the array, while the left pointer j contracts the window whenever the frequency constraint is violated. A hash map tracks the frequency of elements in the current window, and the maximum valid window size encountered is returned as the answer.

Intuition

The key insight is recognizing this as a sliding window problem. We need to find the longest contiguous subarray where no element appears more than k times.

Think of it like maintaining a flexible window that can expand and contract. We want to make this window as large as possible while ensuring it remains "good" (no element frequency exceeds k).

We can start with an empty window and gradually expand it by adding elements from the right. As we add each element, we track its frequency using a hash map. This allows us to know instantly if adding an element violates our constraint.

When we encounter a violation (some element's frequency becomes greater than k), we need to fix it. The question is: how do we fix it efficiently? Instead of starting over, we can shrink the window from the left side. We keep removing elements from the left until the problematic element's frequency drops back to k or below.

Why does this work? Because once we've found a valid window of a certain size, we don't need to check smaller windows anymore - we're looking for the maximum length. So we only shrink the window when absolutely necessary (when the constraint is violated), and we shrink it just enough to make it valid again.

This gives us a two-pointer approach: the right pointer (i) continuously expands the window by moving forward through the array, while the left pointer (j) only moves when needed to maintain validity. At each step, we update our answer with the current valid window size i - j + 1.

The beauty of this approach is that each element is visited at most twice (once by each pointer), giving us an efficient linear time solution.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window solution using two pointers to find the longest good subarray.

Data Structures Used:

• A hash map (defaultdict(int)) to track the frequency of each element in the current window
• Two pointers: j (left boundary) and i (right boundary) of the sliding window

Algorithm Steps:

1. Initialize variables:

   • cnt: A default dictionary to store element frequencies in the current window
   • ans: To track the maximum length found so far, initialized to 0
   • j: Left pointer of the window, initialized to 0

2. Expand the window (right pointer movement):

   • Iterate through the array using enumerate to get both index i and element x
   • For each element x, increment its count: cnt[x] += 1

3. Contract the window when needed (left pointer movement):

   • After adding element x, check if its frequency exceeds k: while cnt[x] > k
   • If violated, shrink the window from the left:
     • Decrement the count of the element at position j: cnt[nums[j]] -= 1
     • Move the left pointer right: j += 1
   • Continue shrinking until cnt[x] <= k (the window becomes valid again)

4. Update the maximum length:

   • After ensuring the window is valid, calculate current window size: i - j + 1
   • Update the answer: ans = max(ans, i - j + 1)

5. Return the result:

   • After processing all elements, return ans

Why this works:

• The right pointer i continuously expands the window by including new elements
• The left pointer j only moves when necessary to maintain the "good" property
• At any point, the subarray from index j to i is guaranteed to be good
• We track the maximum valid window size throughout the process

Time Complexity: O(n) where n is the length of the array, as each element is visited at most twice (once by each pointer)

Space Complexity: O(m) where m is the number of unique elements in the array, for storing the frequency map

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 1, 2, 1, 3] and k = 2.

We'll track the sliding window with pointers j (left) and i (right), maintaining a frequency map cnt for elements in the current window.

Initial state:

• j = 0, ans = 0, cnt = {}

Step 1: i = 0, x = 1

• Add 1 to window: cnt = {1: 1}
• Check: cnt[1] = 1 ≤ 2 ✓ (valid)
• Update answer: ans = max(0, 0-0+1) = 1
• Window: [1]

Step 2: i = 1, x = 2

• Add 2 to window: cnt = {1: 1, 2: 1}
• Check: cnt[2] = 1 ≤ 2 ✓ (valid)
• Update answer: ans = max(1, 1-0+1) = 2
• Window: [1, 2]

Step 3: i = 2, x = 1

• Add 1 to window: cnt = {1: 2, 2: 1}
• Check: cnt[1] = 2 ≤ 2 ✓ (valid)
• Update answer: ans = max(2, 2-0+1) = 3
• Window: [1, 2, 1]

Step 4: i = 3, x = 2

• Add 2 to window: cnt = {1: 2, 2: 2}
• Check: cnt[2] = 2 ≤ 2 ✓ (valid)
• Update answer: ans = max(3, 3-0+1) = 4
• Window: [1, 2, 1, 2]

Step 5: i = 4, x = 1

• Add 1 to window: cnt = {1: 3, 2: 2}
• Check: cnt[1] = 3 > 2 ✗ (violated!)
• Shrink window from left:
  • Remove nums[0] = 1: cnt = {1: 2, 2: 2}, j = 1
  • Check: cnt[1] = 2 ≤ 2 ✓ (now valid)
• Update answer: ans = max(4, 4-1+1) = 4
• Window: [2, 1, 2, 1]

Step 6: i = 5, x = 3

• Add 3 to window: cnt = {1: 2, 2: 2, 3: 1}
• Check: cnt[3] = 1 ≤ 2 ✓ (valid)
• Update answer: ans = max(4, 5-1+1) = 5
• Window: [2, 1, 2, 1, 3]

Final Answer: 5

The longest good subarray is [2, 1, 2, 1, 3] with length 5, where no element appears more than k = 2 times.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers. The outer loop iterates through each element in nums exactly once using enumerate(), giving us n iterations. The inner while loop might seem to add complexity, but each element can only be removed from the window once (when j pointer moves past it). Therefore, the j pointer moves at most n times throughout the entire execution. This means each element is visited at most twice - once when added to the window (by i) and once when removed (by j). The total operations are thus O(2n) = O(n).

Space Complexity: O(n)

The space is dominated by the cnt dictionary (implemented as defaultdict(int)), which stores the frequency count of elements in the current window. In the worst case, all elements in nums are unique and appear in the window simultaneously, requiring the dictionary to store n distinct key-value pairs. Additional variables (ans, j, i, x) use constant space O(1). Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to shrink the window for the specific violating element

A common mistake is checking if ANY element in the window exceeds frequency k, rather than specifically checking the element that was just added. This leads to incorrect window shrinking logic.

Incorrect approach:

# Wrong: Checking all elements in frequency map
for right, current_num in enumerate(nums):
    frequency_map[current_num] += 1
  
    # This checks ALL elements, not just the one we added
    for num, freq in frequency_map.items():
        while freq > k:
            frequency_map[nums[left]] -= 1
            left += 1

Correct approach:

# Right: Only check the element that was just added
for right, current_num in enumerate(nums):
    frequency_map[current_num] += 1
  
    # Only shrink if the CURRENT element violates the constraint
    while frequency_map[current_num] > k:
        frequency_map[nums[left]] -= 1
        left += 1

2. Not handling the case when frequency becomes zero

While not critical for correctness, failing to remove elements with zero frequency from the hash map can lead to unnecessary memory usage in cases with many unique elements.

Better practice:

while frequency_map[current_num] > k:
    frequency_map[nums[left]] -= 1
    # Clean up zero-frequency entries to save memory
    if frequency_map[nums[left]] == 0:
        del frequency_map[nums[left]]
    left += 1

3. Off-by-one error in calculating window size

A frequent mistake is calculating the window size as right - left instead of right - left + 1.

Incorrect:

max_length = max(max_length, right - left)  # Wrong!

Correct:

max_length = max(max_length, right - left + 1)  # Correct!

4. Using regular dictionary instead of defaultdict

Using a regular dictionary requires checking if a key exists before incrementing, which adds complexity and potential for errors.

Error-prone approach:

frequency_map = {}
for right, current_num in enumerate(nums):
    # Need to check if key exists first
    if current_num not in frequency_map:
        frequency_map[current_num] = 0
    frequency_map[current_num] += 1

Cleaner approach:

frequency_map = defaultdict(int)
for right, current_num in enumerate(nums):
    # No need to check - defaultdict handles it
    frequency_map[current_num] += 1