We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Detect Pattern of Length M Repeated K or More Times

Difficulty: Easy

Problem Description

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. Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Key Insights

  • We need to identify subarrays of a specific length m within the given array.
  • The identified subarray must be repeated k or more times consecutively.
  • We can iterate through the array and check for patterns in the specified length.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array, as we need to traverse the array to check for patterns. Space Complexity: O(1) as we are using a constant amount of extra space.

Solution

To solve this problem, we can utilize a sliding window approach to check for patterns in the array:

  1. Iterate through the array while checking for subarrays of length m.
  2. For each potential starting point of the pattern, check if the subsequent elements match this subarray.
  3. Count the number of consecutive repetitions of the pattern.
  4. If the count meets or exceeds k, return true.
  5. If no such pattern is found after checking all possibilities, return false.

Code Solutions

def containsPattern(arr, m, k):
    n = len(arr)
    for i in range(n - m * k + 1):
        count = 0
        while count < k and arr[i:i + m] == arr[i + count * m:i + (count + 1) * m]:
            count += 1
        if count >= k:
            return True
    return False
← Back to All Questions