LeetCode Problem 3641

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

LeetCode 3641 - Longest Semi-Repeating Subarray

Problem Understanding

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

A subarray is considered semi-repeating if the number of distinct values that appear more than once inside that subarray is at most k.

To understand this carefully, consider a frequency map for a subarray:

• If a value appears exactly once, it does not contribute to the repeating count.
• If a value appears two or more times, it contributes exactly one to the repeating count.
• The total number of such values must be at most k.

For example:

• [1,2,3,4] has no repeating elements, so the repeating count is 0.
• [1,2,1,3] has one repeating element (1), so the repeating count is 1.
• [1,2,1,2,3] has two repeating elements (1 and 2), so the repeating count is 2.

The goal is to find the maximum length among all contiguous subarrays satisfying this condition.

The constraints are important:

• 1 <= nums.length <= 100000
• 1 <= nums[i] <= 100000

Since n can be as large as 100000, any algorithm worse than roughly O(n log n) is likely too slow. In particular, quadratic solutions will not finish within the time limit.

Several edge cases immediately stand out:

• k = 0, meaning every valid subarray must contain only unique values.
• All elements are identical.
• All elements are distinct.
• Large blocks of duplicates where the window must repeatedly shrink.
• k larger than the number of repeating values in the entire array, making the whole array valid.

These observations suggest that we need a linear-time sliding window solution.

Approaches

Brute Force

A straightforward solution is to examine every possible subarray.

For each starting index, extend the ending index one position at a time while maintaining frequencies of values in the current subarray. We can track how many distinct values currently have frequency at least two.

Whenever the repeating count is at most k, we update the answer.

This approach is correct because it explicitly checks every possible subarray and therefore cannot miss the optimal one.

However, there are O(n²) subarrays. Even with incremental frequency maintenance, the overall complexity remains O(n²), which is far too slow when n = 100000.

Key Insight

The condition "at most k repeating elements" is a classic sliding window property.

Suppose we have a valid window [left, right].

When we extend the window by moving right, only one element's frequency changes. Therefore, the number of repeating values changes in a predictable way.

If the window becomes invalid, we can move left forward until it becomes valid again.

This works because:

• Expanding the window only increases frequencies.
• Shrinking the window only decreases frequencies.
• The validity condition depends entirely on frequencies within the current window.

Since each pointer moves only forward, we obtain an efficient linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Examines all subarrays
Optimal	O(n)	O(n)	Sliding window with frequency counting

Algorithm Walkthrough

Step 1: Maintain a frequency map

Use a hash map freq where:

• Key = number in the current window
• Value = frequency of that number

This allows constant-time updates when elements enter or leave the window.

Step 2: Track the number of repeating values

Maintain a variable repeating.

A value contributes to repeating if its frequency is at least 2.

When adding a number:

• Increase its frequency.
• If its frequency becomes exactly 2, it has just started repeating.
• Increment repeating.

When removing a number:

• If its frequency is currently 2, removing it will reduce the frequency to 1.
• It will stop being a repeating value.
• Decrement repeating.
• Then decrease its frequency.

Step 3: Expand the right boundary

Iterate through the array using right.

For each new element:

• Add it to the frequency map.
• Update repeating if necessary.

Step 4: Restore validity

If repeating > k, the window is invalid.

Move left forward until:

• repeating <= k

During each removal:

• Update repeating when a frequency drops from 2 to 1.
• Decrease the frequency count.
• Advance left.

Step 5: Update the answer

After the window becomes valid:

• Compute its length as right - left + 1.
• Update the maximum answer.

Step 6: Continue until the end

Repeat the process for every position of right.

The largest valid window encountered is the answer.

Why it works

The sliding window always maintains the invariant that the current window contains at most k repeating values. Whenever the window becomes invalid, the left boundary advances until validity is restored. Since every valid window ending at a given right is represented by the smallest possible valid left, the algorithm never misses a candidate for the maximum length. Because each index enters and leaves the window at most once, the solution remains linear.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def longestSubarray(self, nums: List[int], k: int) -> int:
        freq = defaultdict(int)

        left = 0
        repeating = 0
        answer = 0

        for right, value in enumerate(nums):
            freq[value] += 1

            if freq[value] == 2:
                repeating += 1

            while repeating > k:
                left_value = nums[left]

                if freq[left_value] == 2:
                    repeating -= 1

                freq[left_value] -= 1
                left += 1

            answer = max(answer, right - left + 1)

        return answer

The implementation directly follows the sliding window strategy.

The hash map freq stores frequencies inside the current window. The variable repeating stores how many distinct values currently have frequency at least two.

Whenever a new value enters the window, its frequency is increased. If the frequency reaches exactly 2, that value becomes a repeating value and repeating is incremented.

If the window becomes invalid, the left side is shrunk. Before decreasing a frequency, we check whether that frequency is currently 2. If it is, removing one occurrence will reduce the count to 1, meaning that value is no longer repeating, so repeating is decremented.

After restoring validity, the current window length is compared against the best answer seen so far.

Go Solution

func longestSubarray(nums []int, k int) int {
	freq := make(map[int]int)

	left := 0
	repeating := 0
	answer := 0

	for right, value := range nums {
		freq[value]++

		if freq[value] == 2 {
			repeating++
		}

		for repeating > k {
			leftValue := nums[left]

			if freq[leftValue] == 2 {
				repeating--
			}

			freq[leftValue]--
			left++
		}

		length := right - left + 1
		if length > answer {
			answer = length
		}
	}

	return answer
}

The Go implementation is nearly identical to the Python version.

A map[int]int is used for frequency counting. Since all counts remain within the array size, integer overflow is not a concern. Go slices already provide efficient indexed access, so no additional data structures are required.

Worked Examples

Example 1

Input:

nums = [1,2,3,1,2,3,4]
k = 2

Right	Value	Window	Frequencies	Repeating	Valid?	Answer
0	1	[1]	{1:1}	0	Yes	1
1	2	[1,2]	{1:1,2:1}	0	Yes	2
2	3	[1,2,3]	{1:1,2:1,3:1}	0	Yes	3
3	1	[1,2,3,1]	{1:2,2:1,3:1}	1	Yes	4
4	2	[1,2,3,1,2]	{1:2,2:2,3:1}	2	Yes	5
5	3	[1,2,3,1,2,3]	{1:2,2:2,3:2}	3	No	5

Now shrink:

Left Removed	New Window	Repeating
1	[2,3,1,2,3]	2

Window length becomes 5.

Continue:

Right	Value	Window	Repeating	Answer
6	4	[2,3,1,2,3,4]	2	6

Final answer = 6.

Example 2

Input:

nums = [1,1,1,1,1]
k = 4

Right	Frequency of 1	Repeating	Answer
0	1	0	1
1	2	1	2
2	3	1	3
3	4	1	4
4	5	1	5

Since 1 <= k, the entire array is valid.

Final answer = 5.

Example 3

Input:

nums = [1,1,1,1,1]
k = 0

Right	Frequency	Repeating	Action
0	1	0	Valid
1	2	1	Shrink
2	2	1	Shrink
3	2	1	Shrink
4	2	1	Shrink

The window can never contain two copies of the same value.

The largest valid window is any single element.

Final answer = 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element enters and leaves the sliding window at most once
Space	O(n)	Frequency map may contain all distinct elements

The key observation is that both pointers move only forward. The right pointer traverses the array once, and the left pointer also advances at most n times. Therefore, the total number of window operations is linear.

Test Cases

from typing import List

s = Solution()

assert s.longestSubarray([1,2,3,1,2,3,4], 2) == 6  # example 1
assert s.longestSubarray([1,1,1,1,1], 4) == 5      # example 2
assert s.longestSubarray([1,1,1,1,1], 0) == 1      # example 3

assert s.longestSubarray([1], 0) == 1              # single element
assert s.longestSubarray([1,2,3,4,5], 0) == 5      # all unique
assert s.longestSubarray([1,2,1,2,3], 2) == 5      # entire array valid
assert s.longestSubarray([1,2,1,2,3], 1) == 3      # must exclude one repeating value
assert s.longestSubarray([1,2,3,1,2,3], 0) == 3    # longest unique subarray
assert s.longestSubarray([7,7,7,7], 1) == 4        # one repeating value allowed
assert s.longestSubarray([7,7,7,7], 0) == 1        # no repeats allowed
assert s.longestSubarray([1,2,2,3,3,4], 2) == 6    # exactly k repeating values
assert s.longestSubarray([1,2,2,3,3,4], 1) == 4    # shrink when two values repeat
assert s.longestSubarray([1,2,3,4,1,2,3,4], 3) == 7 # large valid window
assert s.longestSubarray([1,2,3,4,1,2,3,4], 4) == 8 # whole array valid

Test	Why
[1,2,3,1,2,3,4], k=2	Official example
[1,1,1,1,1], k=4	Entire array valid despite many duplicates
[1,1,1,1,1], k=0	No repeats allowed
[1], k=0	Minimum size input
[1,2,3,4,5], k=0	All elements distinct
[1,2,1,2,3], k=2	Whole array satisfies constraint
[1,2,1,2,3], k=1	Window must shrink
[1,2,3,1,2,3], k=0	Classic unique-subarray behavior
[7,7,7,7], k=1	One repeating value allowed
[7,7,7,7], k=0	Repeated single value edge case
[1,2,2,3,3,4], k=2	Exactly at the limit
[1,2,2,3,3,4], k=1	Exceeds limit and must shrink
[1,2,3,4,1,2,3,4], k=3	Large near-optimal window
[1,2,3,4,1,2,3,4], k=4	Entire array valid

Edge Cases

k = 0

When k is zero, no value may appear more than once in the window. The problem effectively becomes finding the longest subarray with all distinct elements. A common bug is forgetting to shrink immediately when the first duplicate appears. The implementation handles this because the while repeating > k loop activates as soon as repeating becomes 1.

All Elements Are Identical

Consider nums = [5,5,5,5,5]. Although the frequency grows very large, the number of repeating values remains exactly 1, because only the value 5 repeats. A buggy implementation might incorrectly count every extra occurrence. The solution correctly increments repeating only when frequency changes from 1 to 2.

Multiple Copies of the Same Number

A value appearing ten times should still contribute only one repeating value. For example, in [1,1,1,1], the repeating count is 1, not 3. The implementation maintains this correctly by modifying repeating only at the transitions 1 → 2 and 2 → 1.

Entire Array Already Valid

If the number of repeating values in the entire array is at most k, the answer should be n. The algorithm naturally handles this case because the shrinking loop never executes, allowing the window to expand across the whole array.

Frequent Shrinking and Expansion

Arrays such as [1,2,3,1,2,3,1,2,3] repeatedly cross the validity threshold. A naive implementation can become quadratic if it recomputes frequencies after every adjustment. The sliding window maintains frequencies incrementally, ensuring that every index is processed only a constant number of times.