#1566

Easy

LeetCode Problem Workspace

Detect Pattern of Length M Repeated K or More Times

Determine if a subarray of length m repeats k or more consecutive times in a given integer array efficiently.

Problem Statement

Given an array of positive integers arr, determine if there exists a contiguous subarray of length m that repeats consecutively k or more times. The pattern must appear in sequence without overlapping other sequences.

Return true if such a repeated pattern exists, otherwise return false. A pattern is defined by its exact length m and the number of consecutive repetitions k, and multiple patterns may exist within the same array, but only one valid occurrence is needed.

Examples

Example 1

Input: arr = [1,2,4,4,4,4], m = 1, k = 3

Output: true

The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2

Output: true

The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3

Input: arr = [1,2,1,2,1,3], m = 2, k = 3

Output: false

The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Constraints

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

Solution Approach

Brute-force Enumeration

Iterate through all possible starting indices of the array. For each index, extract a subarray of length m and check if it repeats k times consecutively by comparing subsequent slices. Return true immediately once a valid repeated pattern is found.

Sliding Window Optimization

Instead of copying slices repeatedly, maintain a moving window and compare elements directly with the expected pattern. This reduces unnecessary memory usage and improves performance for larger arrays within the given constraints.

Early Termination and Pattern Tracking

Keep track of the current repetition count while iterating. If a mismatch occurs, reset the count and move to the next potential starting index. This approach avoids full re-checks of previous positions and handles edge cases where patterns partially overlap with the next segment.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*m) due to iterating over each starting index and comparing up to m elements for each repetition check. Space complexity is O(1) extra since comparisons can be done in place without additional storage.

What Interviewers Usually Probe

Looking for awareness of pattern repetition and consecutive subarray detection.
Checking if you handle overlaps and edge cases correctly when counting repetitions.
Evaluating whether the candidate optimizes comparisons instead of naïve slice copying.

Common Pitfalls or Variants

Common pitfalls

Not verifying consecutive repetitions correctly, leading to false positives.
Incorrectly handling overlaps or resetting the repetition count at wrong positions.
Assuming any repeated sequence counts without enforcing exact length m and minimum k repetitions.

Follow-up variants

Check for repeated patterns allowing gaps between repetitions rather than strictly consecutive.
Count the total number of different patterns of length m repeated at least k times.
Detect the longest pattern that is repeated consecutively at least k times and return its length.

FAQ

What does "Detect Pattern of Length M Repeated K or More Times" mean in simpler terms?

It means finding a contiguous subarray of length m that repeats itself consecutively at least k times in the array.

Can patterns overlap when checking repetitions?

No, each repetition must start immediately after the previous one, so overlaps are not allowed.

What is the most efficient approach for this problem?

Use a nested loop to iterate starting indices and compare elements directly without copying slices, tracking repetition count to terminate early.

Are there constraints on array elements for this pattern detection?

Yes, all elements are positive integers, and array length ranges from 2 to 100, which allows simple nested iteration to be efficient.

How does GhostInterview guide solving this exact pattern problem?

It emphasizes checking every possible subarray of length m, counting consecutive repetitions, and handling edge cases without missing valid patterns.

terminal

Solution

Solution 1: Single Traversal

First, if the length of the array is less than $m \times k$, then there is definitely no pattern of length $m$ that repeats at least $k$ times, so we directly return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#1534 count good triplets #1601 maximum number of achievable transfer requests #1620 coordinate with maximum network quality