LeetCode 1566. Detect Pattern of Length M Repeated K or More Times Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Constraints:

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

Solutions

Solution 1: Single Traversal

First, if the length of the array is less than m × k, then there is definitely no pattern of length m that repeats at least k times, so we directly return false.

Next, we define a variable cnt to record the current count of consecutive repetitions. If there are (k - 1) × m consecutive elements a_i in the array such that a_i = a_{i - m}, then we have found a pattern of length m that repeats at least k times, and we return true. Otherwise, we reset cnt to 0 and continue traversing the array.

Finally, if we finish traversing the array without finding a pattern that meets the conditions, we return false.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

PythonJavaC++GoTypeScript

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

class Solution { public boolean containsPattern(int[] arr, int m, int k) { if (arr.length < m * k) { return false; } int cnt = 0, target = (k - 1) * m; for (int i = m; i < arr.length; ++i) { if (arr[i] == arr[i - m]) { if (++cnt == target) { return true; } } else { cnt = 0; } } return false; } }(code-box)

class Solution { public: bool containsPattern(vector<int>& arr, int m, int k) { if (arr.size() < m * k) { return false; } int cnt = 0, target = (k - 1) * m; for (int i = m; i < arr.size(); ++i) { if (arr[i] == arr[i - m]) { if (++cnt == target) { return true; } } else { cnt = 0; } } return false; } };(code-box)

func containsPattern(arr []int, m int, k int) bool { cnt, target := 0, (k-1)*m for i := m; i < len(arr); i++ { if arr[i] == arr[i-m] { cnt++ if cnt == target { return true } } else { cnt = 0 } } return false }(code-box)

function containsPattern(arr: number[], m: number, k: number): boolean { if (arr.length < m * k) { return false; } const target = (k - 1) * m; let cnt = 0; for (let i = m; i < arr.length; ++i) { if (arr[i] === arr[i - m]) { if (++cnt === target) { return true; } } else { cnt = 0; } } return false; }(code-box)