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.

Example 4:
Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:
Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

 
Constraints:

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Source: leetcode | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        

Solutions:
import queue

class Solution:

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


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		l = list(map(str, arr))
		n = len(l)
		for i in range(n - m + 1):
			d = []
			for j in range(i, n, m):
				x = l[j:j + m]
				print(x)
				if len(x) >= m:
					if d == []:
						d.append(x)
					elif d[-1] == x:
						d.append(x)
						if len(d) >= k:
							return True
					else:
						d = [x]
		return False


class Solution:

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


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		if arr is None:
			return False
		if m <= len(arr) and k * m <= len(arr):
			for s in range(len(arr) - m):
				rec = {}
				for i in range(s, len(arr) - m + 1):
					if tuple(arr[i:i + m]) not in rec:
						rec[tuple(arr[i:i + m])] = 1
					elif arr[i:i + m] == arr[i - m:i]:
						rec[tuple(arr[i:i + m])] += 1
					else:
						break
				tmp = list(rec.values())
				if k in tmp:
					return True
		return False


class Solution:

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


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		for i in range(len(arr) - m + 1):
			p = arr[i:i + m]
			c = 1
			for j in range(i + m, len(arr) - m + 1):
				if arr[j:j + m] == p:
					c += 1
					if c == k:
						return True
				else:
					break
		return False


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		L = len(arr)
		for i in range(L - m * k + 1):
			offset = 0
			iFlag = True
			for ki in range(1, k):
				offset += m
				kFlag = True
				for mi in range(m):
					if arr[i + mi] != arr[i + offset + mi]:
						kFlag = False
						break
				if not kFlag:
					iFlag = False
					break
			if iFlag:
				return True
		return False


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		n = len(arr)
		if n < m * k:
			return False

		def is_matched(a, b, c):
			if c == 0:
				return True
			if arr[b:b + m] != arr[a:a + m]:
				return False
			return is_matched(a, b + m, c - 1)
		for a in range(0, n - k * m + 1):
			if is_matched(a, a + m, k - 1):
				return True
		return False


class Solution:

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


class Solution:

	def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
		arrstr = [str(v) for v in arr]
		patterns = defaultdict(int)
		start = end = 0
		n = len(arrstr)
		while end < n:
			if end - start + 1 > m:
				start += 1
			if end - start + 1 == m:
				substring = ','.join(arrstr[start:end + 1])
				pstart = start - m
				if pstart >= 0 and ','.join(arrstr[pstart:start]) == substring:
					patterns[substring] += 1
				else:
					patterns[substring] = 1
				if patterns[substring] >= k:
					return True
			end += 1
		return False


class Solution:

	def containsPattern(self, arr: List[int], k: int, m: int) -> bool:
		i = 0
		n = len(arr)
		while i + k < n:
			s = 0
			c = i
			lx = arr[c:c + k]
			while c + k <= n:
				if lx == arr[c:c + k]:
					s += 1
				else:
					break
				c += k
			if s >= m:
				return True
			i += 1
		return False