Detect Pattern of Length M Repeated K or More Times Easy

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.
Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.
Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.
 

Constraints:


Solution:

naive:

class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        int n = arr.length;
        if (n < m * k) return false;
        for (int i = 0; i < n; i ++) {
            if (i + m > n) return false;
            List<Integer> p = new ArrayList();
            int count = 1;
            for (int j = i; j < i + m; j ++) {
                p.add(arr[j]);
            }
            while (true) {
                int q = i + count * m;
                List<Integer> curr = new ArrayList();
                // System.out.println(p);
                // System.out.println(q);
                if (q + m > n) break;
                for (int qs = q; qs < q + m; qs ++) {
                    curr.add(arr[qs]);
                }
                // System.out.println(curr);
                if (curr.equals(p)) {
                    count ++;
                } else {
                    break;
                }
                // System.out.println(count);
                if (count >= k) return true;
            }
        }
        return false;
        
    }
}

O(n)

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