Skip to main content
Talentd

Longest Semi-Repeating Subarray - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableSliding Window10 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 105
  • 0 <= k <= nums.length

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray ExpansionO(n²)O(1)Useful for understanding the constraint and validating logic during initial problem exploration
Sliding Window with Adjacent Pair CounterO(n)O(1)Best general solution for large arrays; each element processed once

Video Solution

leetcode 3641 Longest Semi Repeating Subarray | two pointer sliding window • Code-Yao • 47 views views

Frequently Asked Questions

Is Longest Semi-Repeating Subarray easy or hard?
The problem is generally categorized as Medium. The main difficulty is recognizing that the constraint can be maintained incrementally with a sliding window instead of recomputing counts for every subarray. Once the pattern is recognized, the implementation is straightforward.
Longest Semi-Repeating Subarray Python/Java solution
Most implementations follow the same sliding window logic regardless of language. Maintain left and right pointers, update a duplicate‑pair counter when adjacent values match, shrink the window when the constraint breaks, and update the maximum length. The FleetCode solution includes implementations in Python, Java, C++, Go, TypeScript, and Rust.
How to solve Longest Semi-Repeating Subarray in O(n)?
Use two pointers representing a dynamic window. Expand the right pointer and increase a counter whenever nums[i] equals nums[i-1]. If the counter becomes greater than one, shift the left pointer forward until the window contains at most one adjacent duplicate pair again. Track the maximum window size during the scan.
What is the best approach for Longest Semi-Repeating Subarray?
The sliding window approach is the most efficient method. Maintain two pointers and track how many adjacent equal pairs exist inside the current window. If the count exceeds one, move the left pointer until the window becomes valid again. This keeps the window valid while scanning the array once in O(n) time and O(1) space.
Is Longest Semi-Repeating Subarray asked at Google/Amazon/Meta?
Sliding window array problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations often involve limiting duplicates, repeated characters, or frequency constraints within a window. Practicing this pattern helps with many real interview questions.
What data structure is used in Longest Semi-Repeating Subarray?
The optimal approach primarily uses the sliding window two‑pointer technique on an array. Only a small integer counter is required to track adjacent duplicate pairs, so no additional data structures are necessary. Some variants may use a hash table if the constraint involves element frequency instead of adjacency.
What is the time complexity of Longest Semi-Repeating Subarray?
The optimal solution runs in O(n) time using a sliding window. Each element enters the window once and leaves at most once while the two pointers move forward. Space complexity remains O(1) because only a small counter for adjacent duplicate pairs is maintained.

Ready to solve this problem?

Practice Longest Semi-Repeating Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays