Detect Pattern of Length M Repeated K or More Times

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.

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 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

Solution

Method 1 – Sliding Window Pattern Check

Intuition

If a pattern of length m is repeated k or more times consecutively, then for any starting index, the subarrays of length m must be equal for k consecutive blocks. We can check for each possible starting index if this is true.

Approach

1. Iterate over all possible starting indices i from 0 to len(arr) - m * k + 1.
2. For each i, check if the subarray arr[i:i+m] repeats k times consecutively.
3. If such a pattern is found, return true.
4. If no such pattern is found, return false.

Code

C++

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

Go

func containsPattern(arr []int, m int, k int) bool {
    n := len(arr)
    for i := 0; i <= n-m*k; i++ {
        ok := true
        for j := 0; j < m*k; j++ {
            if arr[i+j] != arr[i+j%m] {
                ok = false
                break
            }
        }
        if ok {
            return true
        }
    }
    return false
}

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

Kotlin

class Solution {
    fun containsPattern(arr: IntArray, m: Int, k: Int): Boolean {
        val n = arr.size
        for (i in 0..n - m * k) {
            var ok = true
            for (j in 0 until m * k) {
                if (arr[i + j] != arr[i + j % m]) {
                    ok = false
                    break
                }
            }
            if (ok) return true
        }
        return false
    }
}

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):
            ok = True
            for j in range(m * k):
                if arr[i + j] != arr[i + j % m + i]:
                    ok = False
                    break
            if ok:
                return True
        return False

Rust

impl Solution {
    pub fn contains_pattern(arr: Vec<i32>, m: i32, k: i32) -> bool {
        let n = arr.len() as i32;
        for i in 0..=n - m * k {
            let mut ok = true;
            for j in 0..m * k {
                if arr[(i + j) as usize] != arr[(i + j % m) as usize] {
                    ok = false;
                    break;
                }
            }
            if ok {
                return true;
            }
        }
        false
    }
}

TypeScript

class Solution {
    containsPattern(arr: number[], m: number, k: number): boolean {
        const n = arr.length;
        for (let i = 0; i <= n - m * k; ++i) {
            let ok = true;
            for (let j = 0; j < m * k; ++j) {
                if (arr[i + j] !== arr[i + (j % m)]) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
}

Complexity

• ⏰ Time complexity: O(n * m * k), where n is the length of arr. For each possible start, we check up to m*k elements.
• 🧺 Space complexity: O(1), as we use only a constant amount of extra space.