Detect Pattern of Length M Repeated K or More Times

This problem can be solved using a sliding window approach.

Python solution:

1
2
3
4
5
6
7

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        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

This works as follows:

  • The function containsPattern takes four parameters: arr (the input array), m (the pattern length), k (the minimum number of repetitions), and returns a boolean indicating whether there exists a pattern of length m that is repeated k or more times.

  • The main part of the function is a loop that iterates over the array arr from the beginning to n - m * k + 1, where n is the length of the array. This is because we need to check patterns of length m * k, and this is the last starting point that leaves enough elements for such a pattern.

  • For each i, it checks if the subarray of arr starting from i with length m * k (arr[i:i + m * k]) is the same as the subarray of arr starting from i with length m (arr[i:i + m]) repeated k times. This is done using the == operator, which in Python compares the contents of the lists, not just their references.

  • If the condition is true for any i, it returns True. If it never finds a match, it returns False after the loop ends.

  • This works because any valid pattern of length m that is repeated k or more times will be a subarray of arr of length m * k.

Readable Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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] != arr[i + m]:
                cnt = 0
            cnt += arr[i] == arr[i + m]
            if cnt == (k - 1) * m:
                return True
        return False

This function checks if there is a pattern of length m that is repeated k or more times in the input array arr. The idea behind the solution is to scan the array, comparing each element with the element m positions ahead. Let’s break down how it works:

  1. Initialize a counter cnt to 0. This counter keeps track of how many consecutive repetitions of a pattern of length m we’ve seen so far.

  2. Loop through the elements in arr up to the index len(arr) - m. We stop m places before the end because we’re always comparing with the element m places ahead.

  3. If the current element arr[i] is not equal to the element m places ahead arr[i + m], then the current pattern has been broken. Reset cnt to 0.

  4. If arr[i] is equal to arr[i + m], increment cnt. This line is equivalent to:

    1
2

    if arr[i] == arr[i + m]:
    cnt += 1

  5. If cnt reaches (k - 1) * m, return True. The reason why it’s (k - 1) * m instead of k * m is because we’re counting additional matches beyond the first one. In other words, when cnt == m, we’ve found k repetitions of a pattern of length m.

  6. If we finish the loop without having returned True, return False. This means no qualifying pattern has been found in arr.

The function will return True as soon as it finds a pattern of length m that repeats k or more times, or False if no such pattern exists.