Watch the video solution for Longest Semi-Repeating Subarray, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Code-Yao has 47 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |