Detect Pattern of Length M Repeated K or More Times solution and explanation
9 more videos on this problem
detect pattern of length m repeated k or more times | leetcode 1566Naresh Gupta · 6:25 · 2K views
LeetCode 1566. Detect Pattern of Length M Repeated K or More Times - Interview Prep Ep 95Fisher Coder · 9:11 · 1K views
1566. Detect Pattern of Length M Repeated K or More Times (Leetcode Easy)Programming Live with Larry · 4:08 · 655 views
LeetCode 1566. [easy] Detect Pattern of Length M Repeated K or More TimesFrancesco Manicardi · 2:28 · 245 views
1566 Detect Pattern of Length M Repeated K or More TimesMath Geeks · 1:59 · 93 views
Leetcode 1566 Detect Pattern of Length M Repeated K or More Times带老婆转码 · 11:02 · 49 views
1566. Detect Pattern of Length M Repeated K or More Times - Python - 1 LineAlgoPrepMaster · 1:27 · 26 views
Leetcode Problem Solution | 1566. Detect Pattern of Length M Repeated K or More Times | HindiCodeholic Ninad · 9:01 · 14 views
LeetCode 1566 | Detect Pattern of Length M Repeated K or More Times | Byte by Byte | Day 12Byte_By_Byte · 11:23 · 8 views
LeetCode 1566: Detect Pattern of Length M Repeated K or More TimesAlitaCode · 27:20 · 4 views
The problem
Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.
A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.
Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.
Example 1:
Input: arr = [1,2,4,4,4,4], m = 1, k = 3 Output: true Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.
Example 2:
Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2 Output: true Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.
Example 3:
Input: arr = [1,2,1,2,1,3], m = 2, k = 3 Output: false Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.
Constraints:
2 <= arr.length <= 1001 <= arr[i] <= 1001 <= m <= 1002 <= k <= 100
Approach overview
Problem Overview: Given an integer array arr, determine whether a pattern of length m appears consecutively at least k times. The pattern must repeat back‑to‑back without gaps. Your job is to scan the array and confirm whether such a repeating block exists.
Approach 1: Sliding Window Approach (O(n * m * k) time, O(1) space)
Iterate through every possible starting index of the array where a pattern of length m * k could fit. Treat the first m elements as the base pattern. Then compare the next m elements with that base pattern, repeating this comparison k-1 times. If all segments match, you found a valid repeating pattern. This method uses straightforward comparisons and works well for small inputs. It relies purely on sequential checks over the array and direct element comparisons.
Approach 2: Pattern Matching by Modulo (O(n) time, O(1) space)
Instead of explicitly comparing entire blocks, compare each element with the element m positions ahead. If arr[i] == arr[i + m], it means the pattern continues. Maintain a counter of consecutive matches. Every time this equality holds, increment the counter; otherwise reset it. Once the counter reaches m * (k - 1), you have verified that the pattern of length m repeats k times consecutively. This transforms the repeated pattern check into a linear scan, making it optimal. The approach uses simple enumeration while comparing elements at a fixed offset.
Recommended for interviews: The modulo comparison approach is typically expected. It reduces nested comparisons into a single pass and achieves O(n) time with constant space. The sliding window method still demonstrates understanding of pattern verification and brute-force reasoning, but the optimized approach shows stronger algorithmic insight.
Approach 1: Sliding Window Approach
This approach uses a sliding window of size m to check for repetitions. We slide this window along the array to take `m` length chunks and check if these chunks repeat `k` times consecutively.
def containsPattern(arr, m, k):
n = len(arr)
for i in range(n - m * k + 1):
if all(arr[i + j] == arr[i + j % m] for j in range(m * k)):
return True
return Falseclass Solution {
public boolean containsPattern(int[] arr, int m, int k) {
for (int i = 0; i <= arr.length - m * k; i++) {
boolean match = true;
for (int j = 0; j < m * k; j++) {
if (arr[i + j] != arr[i + j % m]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
}#include <vector>
using namespace std;
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size();
for (int i = 0; i <= n - m * k; i++) {
bool match = true;
for (int j = 0; j < m * k; j++) {
if (arr[i + j] != arr[i + j % m]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}function containsPattern(arr, m, k) {
for (let i = 0; i <= arr.length - m * k; i++) {
if (Array(m * k).fill().every((_, j) => arr[i + j] === arr[i + j % m])) {
return true;
}
}
return false;
}#include <stdbool.h>
bool containsPattern(int* arr, int arrSize, int m, int k) {
for (int i = 0; i <= arrSize - m * k; i++) {
bool match = true;
for (int j = 0; j < m * k; j++) {
if (arr[i + j] != arr[i + j % m]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}public class Solution {
public bool ContainsPattern(int[] arr, int m, int k) {
for (int i = 0; i <= arr.Length - m * k; i++) {
bool match = true;
for (int j = 0; j < m * k; j++) {
if (arr[i + j] != arr[i + j % m]) {
match = false;
break;
}
}
if (match) return true;
}
return false;
}
}The Python solution uses the same strategy as other languages. It loops over possible starting indices and checks for patterns that repeat the required number of times.
Time Complexity: O(n*m*k) where n is the length of the array.
Space Complexity: O(1) because the algorithm itself doesn't require additional space.
Approach 2: Pattern Matching by Modulo
This approach is based on exploiting the modulo operation to compare segments of the array directly. For each starting index, compare elements on a modulo basis within the allowed bounds.
def containsPattern(arr, m, k):
n = len(arr)
for i in range(n - m * k + 1):
if all(arr[i + j] == arr[i + j + m] for j in range(m * (k - 1))):
return True
return Falseclass Solution {
public boolean containsPattern(int[] arr, int m, int k) {
for (int i = 0; i <= arr.length - m * k; i++) {
boolean pattern = true;
for (int j = 0; j < m * (k - 1); ++j) {
if (arr[i + j] != arr[i + j + m]) {
pattern = false;
break;
}
}
if (pattern) return true;
}
return false;
}
}#include <vector>
using namespace std;
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size();
for (int i = 0; i <= n - m * k; i++) {
bool found = true;
for (int j = 0; j < m * (k - 1); ++j) {
if (arr[i + j] != arr[i + j + m]) {
found = false;
break;
}
}
if (found) return true;
}
return false;
}function containsPattern(arr, m, k) {
for (let i = 0; i <= arr.length - m * k; i++) {
if ([...Array(m * (k - 1))].every((_, j) => arr[i + j] === arr[i + j + m])) {
return true;
}
}
return false;
}#include <stdbool.h>
bool containsPattern(int* arr, int arrSize, int m, int k) {
for (int i = 0; i <= arrSize - m * k; i++) {
bool isPattern = true;
for (int j = 0; j < m * (k - 1); ++j) {
if (arr[i + j] != arr[i + j + m]) {
isPattern = false;
break;
}
}
if (isPattern) return true;
}
return false;
}public class Solution {
public bool ContainsPattern(int[] arr, int m, int k) {
for (int i = 0; i <= arr.Length - m * k; i++) {
bool matches = true;
for (int j = 0; j < m * (k - 1); ++j) {
if (arr[i + j] != arr[i + j + m]) {
matches = false;
break;
}
}
if (matches) return true;
}
return false;
}
}Python's approach is similar via list comprehensions, ensuring segments in the sequence match by looking for misalignments that invalidate a potential pattern.
Time Complexity: O(n*m) for an n length array.
Space Complexity: O(1) as no extra structures are essential.
Approach 3: Single Traversal
First, if the length of the array is less than m times k, then there is definitely no pattern of length m that repeats at least k times, so we directly return false.
Next, we define a variable cnt to record the current count of consecutive repetitions. If there are (k - 1) times m consecutive elements a_i in the array such that a_i = a_{i - m}, then we have found a pattern of length m that repeats at least k times, and we return true. Otherwise, we reset cnt to 0 and continue traversing the array.
Finally, if we finish traversing the array without finding a pattern that meets the conditions, we return false.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function containsPattern(arr: number[], m: number, k: number): boolean {
if (arr.length < m * k) {
return false;
}
const target = (k - 1) * m;
let cnt = 0;
for (let i = m; i < arr.length; ++i) {
if (arr[i] === arr[i - m]) {
if (++cnt === target) {
return true;
}
} else {
cnt = 0;
}
}
return false;
}func containsPattern(arr []int, m int, k int) bool {
cnt, target := 0, (k-1)*m
for i := m; i < len(arr); i++ {
if arr[i] == arr[i-m] {
cnt++
if cnt == target {
return true
}
} else {
cnt = 0
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n*m*k) where n is the length of the array. |
| Pattern Matching by Modulo | Time Complexity: O(n*m) for an n length array. |
| Single Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Pattern Check | O(n * m * k) | O(1) | When starting with a direct brute-force comparison or explaining the problem step-by-step in interviews |
| Modulo Pattern Matching | O(n) | O(1) | Best general solution for large arrays; avoids repeated block comparisons |
Frequently asked questions
Is Detect Pattern of Length M Repeated K or More Times easy or hard?
Detect Pattern of Length M Repeated K or More Times is classified as an Easy problem on LeetCode with an acceptance rate around 43%. The main challenge is recognizing that repeated block comparison can be simplified using offset comparisons for an O(n) solution.
Detect Pattern of Length M Repeated K or More Times Python/Java solution
Both Python and Java implementations follow the same logic: iterate from index 0 to n - m - 1, compare arr[i] with arr[i + m], and maintain a running match counter. When the counter reaches m * (k - 1), return true. Otherwise continue scanning until the array ends.
How to solve Detect Pattern of Length M Repeated K or More Times in O(n)?
Scan the array while comparing arr[i] with arr[i + m]. If the values match, increment a counter; otherwise reset it. Once the counter reaches m * (k - 1), the pattern has repeated k times consecutively. This avoids checking every block separately and completes in a single linear pass.
What is the best approach for Detect Pattern of Length M Repeated K or More Times?
The most efficient approach uses modulo-style comparison. Iterate through the array and compare arr[i] with arr[i + m]. Count consecutive matches and check whether the count reaches m * (k - 1). This confirms that the pattern of length m repeats k times. The algorithm runs in O(n) time and uses O(1) space.
Is Detect Pattern of Length M Repeated K or More Times asked at Google/Amazon/Meta?
Pattern detection and repeated sequence problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may not always appear, the underlying idea of recognizing repeated subarrays and optimizing comparisons is a common array interview pattern.
What data structure is used in Detect Pattern of Length M Repeated K or More Times?
The problem mainly uses arrays and index-based comparisons. No additional data structures are required because the optimized approach only compares elements separated by a fixed distance m while scanning the array once.
What is the time complexity of Detect Pattern of Length M Repeated K or More Times?
The optimal solution runs in O(n) time with O(1) extra space. Each element is compared with the element m positions ahead exactly once. A brute-force sliding window approach may take O(n * m * k) time because it repeatedly compares entire pattern segments.