Leetcode – Detect Pattern of Length M Repeated K or More Times Solution

Spread the love

Patterns are a fascinating subject, ubiquitous in mathematics, nature, and computer science. They provide structure and help us make sense of data. The problem of “Detect Pattern of Length M Repeated K or More Times” on Leetcode challenges us to identify repeating patterns in an array. This problem falls under the domain of array manipulation and pattern recognition, often serving as a great way to hone skills in these areas.

This article will provide a comprehensive examination of multiple approaches to solve the problem, analyze their time and space complexities, and consider their respective merits and demerits.

Problem Statement

Given an array of positive integers arr and two integers m and k, the task is to determine if the array contains a pattern of length m that is repeated k or more times.

A repeating pattern of an array is a subarray that consists of one or more chunks (also known as “subarrays”) that are concatenated together. For a subarray chunk to be a part of a repeating pattern, it should occur in the array consecutively and must appear k or more times.

Constraints:

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

Example

Given arr = [1, 2, 4, 4, 4, 4], m = 1, k = 3, the answer is True as the pattern [4] is repeated 4 times, which is greater than or equal to k.

Naive Approach: Brute-force

Algorithm:

  1. Iterate through the array and identify all possible subarrays of length m.
  2. For each subarray, count how many times it appears consecutively in the array.
  3. If any subarray appears k or more times, return True.

Python Implementation:

def containsPattern(arr, m, k):
    n = len(arr)
    for i in range(n - m * k + 1):
        if all(arr[i + j] == arr[i + j % m] for j in range(m * k)):
            return True
    return False

Time Complexity:

The time complexity is O(n×m×k).

Space Complexity:

The space complexity is O(1).

Optimized Approach: Sliding Window

Algorithm:

  1. Use a sliding window of size m to track a pattern.
  2. Compare this pattern with the next k-1 patterns in the array. If they all match, return True.

Python Implementation:

def containsPattern(arr, m, k):
    n = len(arr)
    for i in range(n - m * k + 1):
        if all(arr[i: i + m] == arr[i + j * m: i + (j + 1) * m] for j in range(1, k)):
            return True
    return False

Time Complexity:

The time complexity is O(n×m×k), which may appear the same as the naive approach, but due to the use of Python’s list slicing, this approach can be faster.

Space Complexity:

The space complexity is O(m) due to slicing.

Comparison of Approaches

Conclusion

The problem of “Detect Pattern of Length M Repeated K or More Times” poses an interesting challenge in terms of array manipulation and pattern recognition. Both approaches we discussed solve the problem effectively but vary slightly in their time and space complexities.

While the naive approach is simpler and uses constant space, the optimized approach, albeit slightly more complex, may run faster because of Python’s internal optimization for list slicing.

Leave a Reply