Detect Pattern of Length M Repeated K or More Times

Difficulty: Easy | Acceptance: 43.90% | Paid: No Topics: Array, Enumeration

Given an array of positive integers arr, return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

A pattern is a subarray (contiguous subsequence) of arr that repeats consecutively without overlap. A pattern is defined by its length m and the number of repetitions k.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Counting Consecutive Matches
• Approach 3: Direct Pattern Check

Examples

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 times consecutively.

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 times consecutively.

Example 3

Input: arr = [1,2,1,2,1,3], m = 2, k = 2
Output: false
Explanation: The pattern [1,2] of length 2 is not repeated 2 times consecutively.

Constraints

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

Brute Force

Intuition Check every possible starting position and verify if the pattern of length m repeats k times consecutively.

Steps

• Iterate through all possible starting positions from 0 to n - m*k
• For each position, check if the pattern repeats k times by comparing elements
• Return true if any valid pattern is found

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

Complexity

• Time: O(n × m × k)
• Space: O(1)
• Notes: Simple but not optimal for larger inputs

Counting Consecutive Matches

Intuition If a pattern of length m repeats k times, then each element at position i must equal the element at position i+m. Count consecutive matches to detect patterns.

Steps

• Iterate through the array comparing each element with the element m positions ahead
• Maintain a count of consecutive matches
• If count reaches m × (k-1), we found a valid pattern

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

Complexity

• Time: O(n × m)
• Space: O(1)
• Notes: Optimal solution with single pass through array

Direct Pattern Check

Intuition Extract the pattern from each starting position and verify if it repeats k times consecutively by direct comparison.

Steps

• Iterate through all valid starting positions
• Extract the pattern of length m from the starting position
• Compare this pattern with subsequent segments of length m
• Return true if all k segments match

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

Complexity

• Time: O(n × m × k)
• Space: O(1)
• Notes: Similar to brute force but with cleaner structure