You are given an integer array nums of length n and an integer k.
A semi‑repeating subarray is a contiguous subarray in which at most k elements repeat (i.e., appear more than once).
Return the length of the longest semi‑repeating subarray in nums.
Example 1:
Input: nums = [1,2,3,1,2,3,4], k = 2
Output: 6
Explanation:
The longest semi-repeating subarray is [2, 3, 1, 2, 3, 4], which has two repeating elements (2 and 3).
Example 2:
Input: nums = [1,1,1,1,1], k = 4
Output: 5
Explanation:
The longest semi-repeating subarray is [1, 1, 1, 1, 1], which has only one repeating element (1).
Example 3:
Input: nums = [1,1,1,1,1], k = 0
Output: 1
Explanation:
The longest semi-repeating subarray is [1], which has no repeating elements.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1050 <= k <= nums.lengthProblem Overview: You need the length of the longest subarray where at most one pair of adjacent elements is equal. A subarray becomes invalid once it contains two different positions i such that nums[i] == nums[i-1]. The goal is to keep the window valid while maximizing its size.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Start each subarray from index i and extend it one element at a time toward the right. While extending, track how many adjacent equal pairs appear inside the current range. The moment the count exceeds one, stop expanding that starting point because any longer subarray will also be invalid. Track the maximum valid length across all starts. This approach is simple and helps you reason about the constraint, but it repeatedly scans overlapping ranges which leads to quadratic time.
Approach 2: Sliding Window with Pair Counter (O(n) time, O(1) space)
Use the classic sliding window technique with two pointers left and right. As the right pointer expands the window, check if nums[right] == nums[right-1]. If true, increase a counter that tracks how many adjacent duplicate pairs exist in the current window. When this counter becomes greater than one, move the left pointer forward until the window becomes valid again. While shrinking, decrease the counter when a duplicate pair leaves the window. Each element enters and leaves the window at most once, which guarantees linear time.
This pattern appears frequently in array problems where a window must satisfy a constraint on duplicates or frequency. Even though the structure is simple, the key insight is recognizing that the constraint depends only on adjacent comparisons, allowing constant space instead of a full hash table. The technique is closely related to other array window problems like longest substring with constraints or limited replacements.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force approach demonstrates that you understand the constraint and can validate subarrays correctly. The optimal two‑pointer method shows you recognize overlapping work and can convert the search into a linear pass, which is the typical signal of strong problem‑solving skills in array and sliding window questions.
We use two pointers l and r to maintain a sliding window, where the right pointer continuously moves to the right, and we use a hash table cnt to record the number of occurrences of each element within the current window.
When the occurrence count of an element changes from 1 to 2, it indicates that there is a new repeating element, so we increment the repeating element counter cur by 1. When the repeating element counter exceeds k, it means the current window does not satisfy the condition, and we need to move the left pointer until the repeating element counter is no greater than k. During the process of moving the left pointer, if the occurrence count of an element changes from 2 to 1, it indicates that there is one less repeating element, so we decrement the repeating element counter by 1. Then, we update the answer, i.e., ans = max(ans, r - l + 1).
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Expansion | O(n²) | O(1) | Useful for understanding the constraint and validating logic during initial problem exploration |
| Sliding Window with Adjacent Pair Counter | O(n) | O(1) | Best general solution for large arrays; each element processed once |
Practice Longest Semi-Repeating Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor