# Detect Pattern of Length M Repeated K or More Times
**Difficulty:** EASY
[External](https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times)
Canonical: https://scaleengineer.com/dsa/problems/detect-pattern-of-length-m-repeated-k-or-more-times
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
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`

# Approaches
## Brute Force Iteration
This approach systematically checks every possible subarray of length `m` to see if it forms a pattern that repeats `k` times consecutively. It's straightforward but involves multiple nested loops, leading to a higher time complexity.
**Time:** O(n * m * k), where `n` is the length of `arr`. The outer loop runs up to `n - m*k` times. The nested loops run `k-1` and `m` times respectively. In the worst case, this is approximately `n * k * m` operations. · **Space:** O(1), as we are not using any extra space that scales with the input size.
**Pros:** Simple to understand and implement.; Correctly solves the problem for the given constraints.
**Cons:** Inefficient due to three nested loops.; Performs many redundant comparisons.
### Explanation
The brute-force method iterates through the array `arr` to find a starting point `i` for a potential pattern. The loop for `i` only needs to go up to `arr.length - m * k`, as any starting point beyond that cannot accommodate a pattern of length `m` repeated `k` times.

For each starting index `i`, we define the pattern as the subarray `arr[i...i+m-1]`. Then, we check the subsequent `k-1` blocks of size `m` to see if they are identical to our initial pattern. A block is considered a match if all its `m` elements are equal to the corresponding elements in the pattern. If we find `k-1` such consecutive matching blocks, it means the pattern is repeated `k` times in total, and we can return `true`.

If the loops complete without finding such a pattern, it means no such pattern exists, and we return `false`.

```java
class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        int n = arr.length;
        if (m * k > n) {
            return false;
        }
        // Iterate through all possible starting points of the pattern sequence
        for (int i = 0; i <= n - m * k; i++) {
            boolean allBlocksMatch = true;
            // Check if the k-1 blocks following the first one match
            for (int j = 1; j < k; j++) {
                // Compare the first block (starting at i) with the j-th block (starting at i + j*m)
                for (int offset = 0; offset < m; offset++) {
                    if (arr[i + offset] != arr[i + j * m + offset]) {
                        allBlocksMatch = false;
                        break;
                    }
                }
                if (!allBlocksMatch) {
                    break;
                }
            }
            if (allBlocksMatch) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
* Get the length of the array, `n`.
* If `m * k > n`, it's impossible to find the pattern, so return `false`.
* Iterate with an index `i` from `0` to `n - m * k`. This `i` is the potential start of the entire `k`-repetition sequence.
* Inside the loop, assume a pattern is found (`allBlocksMatch = true`).
* Start a nested loop with index `j` from `1` to `k-1`. This loop checks the `k-1` subsequent blocks.
* Start another nested loop with index `offset` from `0` to `m-1`. This loop compares elements within a block.
* Compare `arr[i + offset]` (element from the first block) with `arr[i + j*m + offset]` (element from the `j`-th block).
* If they are not equal, the pattern is broken. Set `allBlocksMatch = false` and break the inner loops.
* If the loops for `j` and `offset` complete with `allBlocksMatch` still `true`, it means we have found a valid pattern. Return `true`.
* If the outer loop for `i` finishes, no pattern was found. Return `false`.

## Single Pass with Consecutive Match Counting
A more efficient approach that solves the problem in a single pass through the array. It cleverly counts consecutive matching elements to identify the repeated pattern, reducing the time complexity significantly.
**Time:** O(n), where `n` is the length of `arr`. We iterate through the array a single time. · **Space:** O(1), as we only use a single integer variable (`count`) for tracking.
**Pros:** Highly efficient with linear time complexity.; Uses constant extra space.; Avoids redundant work by checking relationships between elements `m` distance apart.
**Cons:** The logic might be slightly less intuitive to grasp initially compared to the direct brute-force approach.
### Explanation
This optimized approach is based on a key observation: a pattern of length `m` is repeated `k` times consecutively if and only if there is a sequence of `(k-1) * m` consecutive indices where each element `arr[i]` is equal to the element `m` positions after it, `arr[i+m]`.

Let's break this down. If we have `k` identical blocks of size `m`, say `B_1, B_2, ..., B_k`, then `B_2` must be identical to `B_1`, `B_3` to `B_2`, and so on. This chain of equalities implies that for every position in blocks `B_2` through `B_k`, the element at that position is the same as the element `m` positions earlier. The total number of elements in blocks `B_2` through `B_k` is `(k-1) * m`.

Therefore, we can solve the problem by iterating through the array and maintaining a `count` of consecutive indices `i` where `arr[i] == arr[i+m]`. If `arr[i]` is not equal to `arr[i+m]`, the streak is broken, and we reset the `count` to zero. If the `count` ever reaches `(k-1) * m`, we have found our pattern, and we can return `true`.

If we finish iterating through the array without the count reaching the target value, no such pattern exists, and we return `false`.

```java
class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        int n = arr.length;
        if (m * k > n) {
            return false;
        }
        int count = 0;
        // We check arr[i] against arr[i+m].
        // The loop runs from i=0 up to the point where i+m is a valid index.
        for (int i = 0; i + m < n; i++) {
            if (arr[i] == arr[i + m]) {
                count++;
            } else {
                count = 0;
            }
            // A pattern is formed by k blocks. This means k-1 repetitions.
            // Each repetition means a block of size m matches the previous one.
            // This requires m consecutive matches of arr[i] == arr[i+m].
            // So, for k-1 repetitions, we need (k-1)*m such consecutive matches.
            if (count == m * (k - 1)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
* Initialize a `count` variable to `0`. This will track the number of consecutive indices `i` where `arr[i]` matches `arr[i+m]`.
* Iterate through the array with an index `i` from `0` to `arr.length - m - 1`.
* At each index `i`, compare `arr[i]` with `arr[i+m]`.
* If `arr[i] == arr[i+m]`, increment `count`.
* If `arr[i] != arr[i+m]`, reset `count` to `0` because the consecutive match streak is broken.
* After updating the count, check if `count` is equal to `m * (k - 1)`.
* If it is, we have found `k-1` consecutive repetitions of a pattern of length `m`. This means we have `k` identical blocks in total. Return `true`.
* If the loop completes without the condition in step 6 being met, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean containsPattern(int[] arr, int m, int k) {
    int n = arr.length;
    for (int i = 0; i <= n - m * k; ++i) {
      int j = 0;
      for (; j < m * k; ++j) {
        if (arr[i + j] != arr[i + (j % m)]) {
          break;
        }
      }
      if (j == m * k) {
        return true;
      }
    }
    return false;
  }
}

```

### Python

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

```

### CPP

```cpp
class Solution {
public:
  bool containsPattern(vector<int> &arr, int m, int k) {
    int n = arr.size();
    for (int i = 0; i <= n - m * k; ++i) {
      int j = 0;
      for (; j < m * k; ++j) {
        if (arr[i + j] != arr[i + (j % m)]) {
          break;
        }
      }
      if (j == m * k) {
        return true;
      }
    }
    return false;
  }
};

```