EasyNo. 1566

Detect Pattern of Length M Repeated K or More Times — LeetCode 1566 Python Solution

Topics
Array, Enumeration
Reading time
3 min

The problem

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.

Example

Input
arr = [1,2,4,4,4,4], m = 1, k = 3
Output
true
Explanation
The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Python solution

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

Complexity

Time
O(n)where n is the length of the array
Space · auxiliary
O(1)

Related problems

Frequently asked questions

How hard is LeetCode 1566. Detect Pattern of Length M Repeated K or More Times?

LeetCode 1566. Detect Pattern of Length M Repeated K or More Times is rated Easy on LeetCode.

What is the time complexity of LeetCode 1566. Detect Pattern of Length M Repeated K or More Times?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 1566. Detect Pattern of Length M Repeated K or More Times?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1566. Detect Pattern of Length M Repeated K or More Times cover?

LeetCode 1566. Detect Pattern of Length M Repeated K or More Times is tagged Array and Enumeration on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.