Problem Description

You are given an integer array nums of length n and an integer k.

A semi-repeating subarray is defined as a contiguous subarray where at most k elements appear more than once (i.e., at most k elements are repeating).

Your task is to find and return the length of the longest semi-repeating subarray in nums.

For example, if you have an array [1, 2, 3, 2, 4, 3, 5] and k = 2, the subarray [1, 2, 3, 2, 4, 3] is valid because exactly 2 elements (2 and 3) appear more than once. However, if we tried to extend it to include 5, making it [1, 2, 3, 2, 4, 3, 5], it would still be valid since we still have only 2 repeating elements.

The key constraint is that you can have at most k distinct values that appear multiple times within any subarray you consider. Elements that appear exactly once in the subarray don't count toward this limit.

Intuition

When we need to find the longest subarray with certain properties, a sliding window approach often works well. The key insight here is that we need to track how many elements are "repeating" (appearing more than once) in our current window.

Think about expanding a window from left to right. As we add new elements, we need to know:

1. Has this element appeared before in our window?
2. If it has appeared exactly once before, adding it now makes it a "repeating" element

The critical observation is that we only care about the transition point - when an element goes from appearing once to appearing twice. That's when it becomes a "repeating" element and contributes to our count.

Similarly, when we shrink the window from the left:

• If removing an element causes its count to drop from 2 to 1, it's no longer "repeating"
• We need to decrease our repeating element counter accordingly

This leads us to maintain:

• A frequency map (cnt) to track occurrences of each element
• A counter (cur) for the number of repeating elements
• When cnt[x] becomes 2, we increment cur
• When cnt[x] drops to 1, we decrement cur

The window remains valid as long as cur <= k. When cur > k, we have too many repeating elements and must shrink the window from the left until the condition is satisfied again.

This two-pointer sliding window technique ensures we explore all possible valid subarrays while maintaining O(n) time complexity, as each element is visited at most twice (once by right pointer, once by left pointer).

Solution Approach

We implement a sliding window technique using two pointers to efficiently find the longest semi-repeating subarray.

Data Structures Used:

• cnt: A hash table (defaultdict) to track the frequency of each element in the current window
• cur: Counter for the number of repeating elements (elements appearing more than once)
• l and r: Left and right pointers defining our sliding window
• ans: Stores the maximum length found so far

Algorithm Steps:

1. Initialize variables:

   • cnt = defaultdict(int) for frequency tracking
   • ans = cur = l = 0 to start with empty window and zero repeating elements

2. Expand the window by moving right pointer:

   for r, x in enumerate(nums):
       cnt[x] += 1
       cur += cnt[x] == 2

   • For each element x at position r, increment its count in cnt
   • If cnt[x] becomes exactly 2, this element just became a repeating element, so increment cur
   • The expression cnt[x] == 2 returns True (1) or False (0), elegantly updating the counter

3. Shrink window when constraint is violated:

   while cur > k:
       cnt[nums[l]] -= 1
       cur -= cnt[nums[l]] == 1
       l += 1

   • When we have more than k repeating elements, shrink from the left
   • Decrement the count of the leftmost element
   • If its count drops to exactly 1, it's no longer repeating, so decrement cur
   • Move the left pointer forward

4. Update the answer:

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

   • After ensuring the window is valid, update ans with the current window size

5. Return the result:

   • After processing all elements, return the maximum length found

Time Complexity: O(n) - Each element is visited at most twice (once by each pointer)

Space Complexity: O(min(n, m)) where m is the number of distinct elements in the array

The beauty of this solution lies in tracking state transitions (1→2 for becoming repeating, 2→1 for stopping repetition) rather than constantly recounting repeating elements, making it highly efficient.

Example Walkthrough

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

We'll track our sliding window with left pointer l and right pointer r, maintaining:

• cnt: frequency map of elements in current window
• cur: count of repeating elements (those appearing > 1 time)
• ans: maximum valid subarray length found

Initial State: l = 0, cur = 0, ans = 0, cnt = {}

Step 1: r = 0, element = 1

• Add 1 to window: cnt = {1: 1}
• cnt[1] becomes 1 (not 2), so cur stays 0
• Window [1] is valid, ans = max(0, 0-0+1) = 1

Step 2: r = 1, element = 2

• Add 2 to window: cnt = {1: 1, 2: 1}
• cnt[2] becomes 1 (not 2), so cur stays 0
• Window [1, 2] is valid, ans = max(1, 1-0+1) = 2

Step 3: r = 2, element = 3

• Add 3 to window: cnt = {1: 1, 2: 1, 3: 1}
• cnt[3] becomes 1 (not 2), so cur stays 0
• Window [1, 2, 3] is valid, ans = max(2, 2-0+1) = 3

Step 4: r = 3, element = 2

• Add 2 to window: cnt = {1: 1, 2: 2, 3: 1}
• cnt[2] becomes 2, so cur = 1 (2 is now repeating)
• Window [1, 2, 3, 2] is valid (cur ≤ k), ans = max(3, 3-0+1) = 4

Step 5: r = 4, element = 4

• Add 4 to window: cnt = {1: 1, 2: 2, 3: 1, 4: 1}
• cnt[4] becomes 1 (not 2), so cur stays 1
• Window [1, 2, 3, 2, 4] is valid, ans = max(4, 4-0+1) = 5

Step 6: r = 5, element = 3

• Add 3 to window: cnt = {1: 1, 2: 2, 3: 2, 4: 1}
• cnt[3] becomes 2, so cur = 2 (3 is now also repeating)
• Window [1, 2, 3, 2, 4, 3] is valid (cur = k), ans = max(5, 5-0+1) = 6

Step 7: r = 6, element = 5

• Add 5 to window: cnt = {1: 1, 2: 2, 3: 2, 4: 1, 5: 1}
• cnt[5] becomes 1 (not 2), so cur stays 2
• Window [1, 2, 3, 2, 4, 3, 5] is valid (cur ≤ k), ans = max(6, 6-0+1) = 7

Final Result: The longest semi-repeating subarray has length 7 (the entire array).

In this example, we have exactly 2 repeating elements (2 and 3), which satisfies our constraint of k = 2. The sliding window never needed to shrink because we never exceeded k repeating elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through the array exactly once via the enumerate function. The left pointer l only moves forward and never backwards, meaning each element is visited at most twice (once by r and once by l). Despite the nested while loop, the total number of operations across all iterations is bounded by 2n, resulting in O(n) time complexity where n is the length of the array nums.

Space Complexity: O(n)

The space complexity is dominated by the defaultdict(int) data structure cnt, which stores the frequency count of elements in the current window. In the worst case, when all elements in the array are distinct, the dictionary could contain up to n unique keys, where n is the length of the array nums. The other variables (ans, cur, l, r, x) use constant space O(1). Therefore, the overall space complexity is O(n).

Common Pitfalls

Pitfall 1: Incorrectly Tracking State Transitions

The Problem: A common mistake is to increment/decrement the duplicate counter at the wrong frequency thresholds. Developers often write:

# INCORRECT - increments for every occurrence beyond the first
if frequency_map[current_num] > 1:
    duplicate_count += 1

This would incorrectly increment duplicate_count every time we see a duplicate, not just when an element transitions from appearing once to appearing twice.

Why It Fails: If we have the array [1, 2, 2, 2], the element 2 would incorrectly contribute 2 to duplicate_count (when going from 1→2 and 2→3), even though it should only count as one repeating element.

The Correct Approach:

# CORRECT - only increments when transitioning from 1 to 2 occurrences
if frequency_map[current_num] == 2:
    duplicate_count += 1

Pitfall 2: Forgetting to Clean Up Zero-Frequency Elements

The Problem: When using a defaultdict, elements with zero frequency remain in the dictionary, potentially causing memory issues with large inputs or when the window slides extensively.

The Fix:

while duplicate_count > k:
    left_num = nums[left_pointer]
    frequency_map[left_num] -= 1
  
    if frequency_map[left_num] == 1:
        duplicate_count -= 1
    # Clean up elements with zero frequency
    elif frequency_map[left_num] == 0:
        del frequency_map[left_num]
  
    left_pointer += 1

Pitfall 3: Off-by-One Error in Window Size Calculation

The Problem: Calculating window size as right_pointer - left_pointer instead of right_pointer - left_pointer + 1.

Why It Matters: For a window from index 2 to 5, the size should be 4 elements (indices 2, 3, 4, 5), not 3.

The Correct Formula:

current_window_size = right_pointer - left_pointer + 1

Pitfall 4: Misunderstanding the Problem Constraint

The Problem: Confusing "at most k elements appear more than once" with:

• "Each element can appear at most k times"
• "The total number of duplicates is at most k"
• "At most k pairs of duplicates"

Clarification: The constraint means we can have at most k distinct values that have frequency > 1 in our window. For example, with k=2:

• Valid: [1, 2, 2, 3, 3, 4] - only elements 2 and 3 repeat
• Invalid: [1, 1, 2, 2, 3, 3] - three elements (1, 2, 3) repeat

Pitfall 5: Not Handling Edge Cases

The Problem: Failing to consider special cases like:

• Empty array or single element array
• k = 0 (no repeating elements allowed)
• All elements are unique
• All elements are the same

Robust Solution Structure:

def longestSubarray(self, nums: List[int], k: int) -> int:
    # Handle edge cases
    if not nums:
        return 0
    if len(nums) == 1:
        return 1
  
    # Main sliding window logic...

These pitfalls highlight the importance of carefully tracking state transitions and understanding exactly what the problem is asking for, rather than making assumptions about the constraint interpretation.