[Leetcode]1566. Detect Pattern of Length M Repeated K or More Times

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.

Brute force

The brute force approach is quite intuitive: starting with each character, we can check whether the following string of length m*k is equal to the following string of length m repeats k or more times. Time complexity is O(nmk) and the space complexity is O(mk).

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

Optimized

We can achieve O(n) time complexity and O(1) space complexity. We would check arr[i]==arr[i+m]. If this is True for k-1 time continuously, then it’s safe to say we’ve found the repeated strings. When this is False, we need to reset the counter as 0.

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

Reference

  • https://leetcode.com/problems/detect-pattern-of-length-m-repeated-k-or-more-times/
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments