Problem Description

Given an array of positive integers arr, and two integers m and k, your task is to determine whether there exists a pattern of length m that is repeated consecutively at least k times in arr.

• The pattern must be a contiguous subarray of length m.
• The pattern must appear consecutively (one after another) at least k times without overlap.
• Elements cannot be reused between patterns (the patterns must be non-overlapping).
• Return true if such a pattern exists, otherwise return false.

Example:
arr = [1,2,4,4,4,4], m = 1, k = 3 → true (because 4 is repeated 4 times, which is more than 3 times)

Constraints:

• 2 ≤ arr.length ≤ 100
• 1 ≤ m ≤ arr.length
• 2 ≤ k ≤ 100
• 0 ≤ arr[i] ≤ 100

Thought Process

The problem asks us to detect if a certain pattern of length m appears k or more times consecutively in the array. The most direct approach would be to check every possible subarray of length m and see if it is repeated k times in a row starting from that position.

At first, it may seem tempting to check all possible patterns and count their occurrences throughout the array. However, the key is that the repetitions must be consecutive and non-overlapping. This constraint means we can focus on each possible starting point, and for each, check if the next k blocks of size m are identical.

To optimize, we avoid checking patterns that cannot possibly fit k times in the remaining part of the array. This saves unnecessary work and keeps our solution efficient.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Iterate over possible starting positions:
   • We loop from index 0 to len(arr) - m * k + 1. This ensures there is enough room for k non-overlapping patterns of length m.
2. Check for consecutive pattern matches:
   • For each starting index, compare the first pattern of length m with the next k-1 blocks of length m.
   • All blocks must match exactly for the pattern to be valid.
3. Return as soon as a valid pattern is found:
   • If all k blocks match, return true immediately.
   • If no such pattern is found after checking all starting positions, return false.

We use simple array slicing or looping to compare subarrays. This approach is efficient because it avoids unnecessary repeated work and only checks valid candidate positions.

Example Walkthrough

Let's walk through an example:

Input: arr = [1,2,1,2,1,2,1,3], m = 2, k = 3

1. The pattern length m is 2, and we need it to repeat k (3) times consecutively.
2. We start at index 0. The first pattern is [1,2].
   • Next block: [1,2] at index 2 (matches)
   • Next block: [1,2] at index 4 (matches)
   Since we found 3 consecutive [1,2] patterns, we return true.
3. If we didn't find such a pattern, we would move to the next starting index and repeat the process.

This process continues until either a valid pattern is found or all possible starting indices are checked.

Time and Space Complexity

• Brute-force approach:
  • For each possible subarray of length m, check every occurrence throughout the array. This can result in O(N^2) time for large arrays, which is inefficient.
• Optimized approach (described above):
  • We iterate over at most N starting points, and for each, compare up to m * k elements (since we compare k blocks of size m).
  • Overall time complexity: O(N * m * k), which is acceptable for the given constraints (N ≤ 100).
  • Space complexity: O(1) extra space (not counting input), since we only use a few variables for indexing and comparison.

Summary

The key to solving this problem is recognizing that only consecutive, non-overlapping patterns matter. By iterating over each possible starting position and checking for k consecutive identical blocks of length m, we efficiently determine if the required pattern exists. This approach is both simple and effective for the problem's constraints, avoiding unnecessary computation and making the code easy to understand and maintain.

Code Implementation

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

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) {
            bool match = true;
            for (int j = 0; j < m; ++j) {
                for (int l = 1; l < k; ++l) {
                    if (arr[i + j] != arr[i + l * m + j]) {
                        match = false;
                        break;
                    }
                }
                if (!match) break;
            }
            if (match) return true;
        }
        return false;
    }
};
      

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

var containsPattern = function(arr, m, k) {
    let n = arr.length;
    for (let i = 0; i <= n - m * k; ++i) {
        let match = true;
        for (let j = 0; j < m; ++j) {
            for (let l = 1; l < k; ++l) {
                if (arr[i + j] !== arr[i + l * m + j]) {
                    match = false;
                    break;
                }
            }
            if (!match) break;
        }
        if (match) return true;
    }
    return false;
};