Problem statement

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

Solution 1

For each possible start of pattern check if arr[i:i+m]*k == arr[i:i+m*k].

Complexity

Time complexity is O(mkn), where n is length of arr, space is O(n).

Code

class Solution:
    def containsPattern(self, arr, m, k):
        return any(arr[i:i+m]*k == arr[i:i+m*k] for i in range(len(arr) - m))

Solution 2

There is also O(mn) solution.

Complexity

It is O(mn) for time and O(n) for space.

Code

class Solution:
    def containsPattern(self, arr, m, k):
        for j in range(m):
            patterns = [arr[i:i + m] for i in range(j, len(arr), m)]
            if any(len(list(j)) >= k for _, j in groupby(patterns)): return True
            
        return False

Solution 3

There is also O(n) solution! Let us calculate sum in each window of size m. Then what we need to find is mk-m+1 adjacent windows with the same sum.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def containsPattern(self, arr, m, k):
        t = [sum(arr[:m])]
        for i in range(len(arr) - m):
            t.append(t[-1] + arr[i+m] - arr[i])
            
        return any(len(list(j)) > m*k - m for _, j in groupby(t))