Detect Pattern of Length M Repeated K or More Times

Easy
1104.

Detect Pattern of Length M Repeated K or More Times

Detect Pattern of Length M Repeated K or More Times is an easy coding problem on arrays and enumeration, asked in Amazon and Google interviews.

A pattern is a contiguous subarray of length m. It is repeated k times when k copies of it appear back to back in arr, without overlapping — that is, some block of m * k consecutive elements is the pattern written k times in a row.

Return true if arr contains a pattern of length m repeated k or more times.

Example 1

Input
arr = [3,5,5,5,5,2], m = 1, k = 3
Output
true
Explanation
The pattern [5] occurs four times in a row.

Example 2

Input
arr = [1,2,1,2,1,3], m = 2, k = 3
Output
false
Explanation
[1,2] occurs twice in a row, then the run breaks.

Example 3

Input
arr = [6,4,6,4,6,4,6,4], m = 2, k = 4
Output
true

Constraints

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • 1 <= m <= 100
  • 2 <= k <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} m
 * @param {number} k
 * @return {boolean}
 */
var containsPattern = function(arr, m, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Detect Pattern of Length M Repeated K or More Times Solution

Detect Pattern of Length M Repeated K or More Times solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Detect Pattern of Length M Repeated K or More Times is an easy coding problem on arrays and enumeration, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Enumeration
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A pattern is a contiguous subarray of length m. It is repeated k times when k copies of it appear back to back in arr, without overlapping — that is, some block of m * k consecutive elements is the pattern written k times in a row.

Return true if arr contains a pattern of length m repeated k or more times.

Example 1

Input: arr = [3,5,5,5,5,2], m = 1, k = 3
Output: true
Explanation: The pattern [5] occurs four times in a row.

Example 2

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: [1,2] occurs twice in a row, then the run breaks.

Example 3

Input: arr = [6,4,6,4,6,4,6,4], m = 2, k = 4
Output: true

Constraints

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • 1 <= m <= 100
  • 2 <= k <= 100

Hints for Detect Pattern of Length M Repeated K or More Times

  1. Hint 1

    A block made of k copies of an m-element pattern is exactly a block of length m * k in which every element equals the one m places later.

  2. Hint 2

    Compare arr[i] with arr[i + m] for every valid i.

  3. Hint 3

    Count how many consecutive indices pass that comparison; reaching (k - 1) * m means you have found the block.

How to solve Detect Pattern of Length M Repeated K or More Times

k back-to-back copies of a length-m pattern form a block of length m * k with period m. Period m over that block means (k - 1) * m consecutive indices i with arr[i] == arr[i + m].

Approach

  1. Set run = 0.
  2. For each i from 0 while i + m < n: if arr[i] == arr[i + m], increment run and return true once it reaches (k - 1) * m; otherwise reset run to 0.
  3. Return false after the scan.

Why it works

If indices s to s + (k - 1) * m - 1 all satisfy arr[i] == arr[i + m], then every element of arr[s .. s + k * m - 1] equals the element m before it, so the block is the first m elements repeated k times. Conversely such a block yields that run of matches. The counter finds any such run in one pass.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • m * k can exceed the array length; the loop then never fires and the answer is false.
  • Reset the run on a mismatch — matches separated by a break do not combine.
  • Copies must not overlap: [1,1,1] holds the pattern [1,1] only once.

Reference solution

Python

from typing import List

def containsPattern(arr: List[int], m: int, k: int) -> bool:
    run = 0
    for i in range(len(arr) - m):
        if arr[i] == arr[i + m]:
            run += 1
            if run == (k - 1) * m:
                return True
        else:
            run = 0
    return False

Java

public static boolean containsPattern(int[] arr, int m, int k) {
    int run = 0;
    for (int i = 0; i + m < arr.length; i++) {
        if (arr[i] == arr[i + m]) {
            run++;
            if (run == (k - 1) * m) return true;
        } else {
            run = 0;
        }
    }
    return false;
}

C++

bool containsPattern(vector<int>& arr, int m, int k) {
    int n = arr.size(), run = 0;
    for (int i = 0; i + m < n; i++) {
        if (arr[i] == arr[i + m]) {
            run++;
            if (run == (k - 1) * m) return true;
        } else {
            run = 0;
        }
    }
    return false;
}

JavaScript

var containsPattern = function(arr, m, k) {
    var run = 0;
    for (var i = 0; i + m < arr.length; i++) {
        if (arr[i] === arr[i + m]) {
            run++;
            if (run === (k - 1) * m) return true;
        } else {
            run = 0;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays