# [Leetcode]1566. Detect Pattern of Length M Repeated K or More Times

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.

#### 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/
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments