LeetCode 1566: Detect Pattern of Length M Repeated K or More Times Solution

Problem Description

Explanation

To solve this problem, we can iterate through all possible patterns of length m in the arr. For each pattern, we check if it is repeated k or more times consecutively in the array. If we find such a pattern, we return true. Otherwise, we return false.

We need to iterate through all possible patterns of length m, which will take O(n) time.
For each pattern, we need to check if it is repeated k or more times, which will also take O(n) time.
Therefore, the overall time complexity of this solution is O(n^2).

The space complexity of this solution is O(1) as we are not using any extra space other than a few variables.

Solutions

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

Problem Description

Explanation

Solutions

Related LeetCode Problems