Given an array of positive integers`arr`

, find a pattern of length`m`

that is repeated`k`

or more times. Apatternis a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple timesconsecutivelywithout 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`

.

#### Brute force

The brute force approach is quite intuitive: starting with each character, we can check whether the following string of length `m*k`

is equal to the following string of length m repeats `k`

or more times. Time complexity is O(nmk) and the space complexity is O(mk).

```
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
if m*k>len(arr):
return False
n = len(arr)
for i in range(n-m*k+1):
if arr[i:i+m*k] == arr[i:i+m]*k:
return True
return False
```

#### Optimized

We can achieve O(n) time complexity and O(1) space complexity. We would check `arr[i]==arr[i+m]`

. If this is `True`

for k-1 time continuously, then it’s safe to say we’ve found the repeated strings. When this is `False`

, we need to reset the counter as `0`

.

```
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
cnt = 0
for i in range(len(arr)-m):
if arr[i+m] != arr[i]:
cnt = 0
else:
cnt += 1
if cnt == m*(k-1):
return True
return False
```

#### Reference

- https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/