Detect Pattern of Length M Repeated K or More Times Solution
Detect Pattern of Length M Repeated K or More Times solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Detect Pattern of Length M Repeated K or More Times is an easy coding problem on arrays and enumeration, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A pattern is a contiguous subarray of length m. It is repeated k times when k copies of it appear back to back in arr, without overlapping — that is, some block of m * k consecutive elements is the pattern written k times in a row.
Return true if arr contains a pattern of length m repeated k or more times.
Example 1
Input: arr = [3,5,5,5,5,2], m = 1, k = 3
Output: true
Explanation: The pattern [5] occurs four times in a row.
Example 2
Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: [1,2] occurs twice in a row, then the run breaks.
Example 3
Input: arr = [6,4,6,4,6,4,6,4], m = 2, k = 4
Output: true
Constraints
2 <= arr.length <= 1001 <= arr[i] <= 1001 <= m <= 1002 <= k <= 100
Hints for Detect Pattern of Length M Repeated K or More Times
Hint 1
A block made of
kcopies of anm-element pattern is exactly a block of lengthm * kin which every element equals the onemplaces later.Hint 2
Compare
arr[i]witharr[i + m]for every validi.Hint 3
Count how many consecutive indices pass that comparison; reaching
(k - 1) * mmeans you have found the block.
How to solve Detect Pattern of Length M Repeated K or More Times
k back-to-back copies of a length-m pattern form a block of length m * k with period m. Period m over that block means (k - 1) * m consecutive indices i with arr[i] == arr[i + m].
Approach
- Set
run = 0. - For each
ifrom 0 whilei + m < n: ifarr[i] == arr[i + m], incrementrunand returntrueonce it reaches(k - 1) * m; otherwise resetrunto 0. - Return
falseafter the scan.
Why it works
If indices s to s + (k - 1) * m - 1 all satisfy arr[i] == arr[i + m], then every element of arr[s .. s + k * m - 1] equals the element m before it, so the block is the first m elements repeated k times. Conversely such a block yields that run of matches. The counter finds any such run in one pass.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
m * kcan exceed the array length; the loop then never fires and the answer isfalse.- Reset the run on a mismatch — matches separated by a break do not combine.
- Copies must not overlap: [1,1,1] holds the pattern [1,1] only once.
Reference solution
Python
from typing import List
def containsPattern(arr: List[int], m: int, k: int) -> bool:
run = 0
for i in range(len(arr) - m):
if arr[i] == arr[i + m]:
run += 1
if run == (k - 1) * m:
return True
else:
run = 0
return FalseJava
public static boolean containsPattern(int[] arr, int m, int k) {
int run = 0;
for (int i = 0; i + m < arr.length; i++) {
if (arr[i] == arr[i + m]) {
run++;
if (run == (k - 1) * m) return true;
} else {
run = 0;
}
}
return false;
}C++
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size(), run = 0;
for (int i = 0; i + m < n; i++) {
if (arr[i] == arr[i + m]) {
run++;
if (run == (k - 1) * m) return true;
} else {
run = 0;
}
}
return false;
}JavaScript
var containsPattern = function(arr, m, k) {
var run = 0;
for (var i = 0; i + m < arr.length; i++) {
if (arr[i] === arr[i + m]) {
run++;
if (run === (k - 1) * m) return true;
} else {
run = 0;
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays