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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Detect Pattern of Length M Repeated K or More Times

Number: 1689

Difficulty: Easy

Paid? No

Companies: Bloomberg, Hudson River Trading

Problem Description

Given an array of positive integers, the task is to determine whether there exists a pattern (i.e., a subarray of length m) that is repeated consecutively k or more times within the array. A pattern must appear as contiguous blocks without overlapping.

Key Insights

  • Iterate through possible starting indices where a pattern of length m repeated k times might exist.
  • For each candidate starting index, compare k consecutive blocks of length m.
  • Only check indices up to arr.length - m*k, because beyond that there aren’t enough elements for k repetitions.
  • Since the input size is limited, a straightforward brute-force check is efficient.

Space and Time Complexity

Time Complexity: O(n * m * k), where n is the length of the array. In the worst case, for each starting index, we compare k-1 blocks of m elements each. Space Complexity: O(1), using only a constant amount of extra space.

Solution

We solve the problem by iterating over the array to check for a potential starting position for the pattern. For each candidate, we verify that the subsequent k-1 blocks of m elements are identical to the initial block. The algorithm uses nested loops: the outer loop over potential starting indices and inner loops for block comparison. By doing this, we cover all possibilities efficiently given the constraints.

Code Solutions

# Python solution to detect a repeating pattern in the array
def containsPattern(arr, m, k):
    n = len(arr)
    # Only iterate till index where k blocks of length m are possible
    for i in range(n - m * k + 1):
        match = True
        # For each block starting from the second one, check if it matches the first block
        for j in range(1, k):
            for l in range(m):
                # if any element mismatches, break out of the loop
                if arr[i + l] != arr[i + j * m + l]:
                    match = False
                    break
            # if this block doesn't match, exit early
            if not match:
                break
        # if k repeating blocks are identical, return True
        if match:
            return True
    return False

# Example usage:
print(containsPattern([1,2,4,4,4,4], 1, 3))  # Expected output: True
← Back to All Questions