LeetCode 1566 - Detect Pattern of Length M Repeated K or More Times

The problem gives us an integer array arr and two integers, m and k. We need to determine whether there exists a contiguous subarray of length m that repeats consecutively at least k times.

leetcodeeasyarrayenumeration

LeetCode Problem 1566

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

Problem Understanding

The problem gives us an integer array arr and two integers, m and k. We need to determine whether there exists a contiguous subarray of length m that repeats consecutively at least k times.

A pattern is considered valid only if:

  • The repeated segments are consecutive
  • Each repeated segment has exactly length m
  • The repetitions do not overlap incorrectly
  • The pattern appears at least k times in a row

For example, if m = 2 and the pattern is [1, 2], then a valid repetition for k = 3 would look like:

[1,2][1,2][1,2]

which corresponds to:

[1,2,1,2,1,2]

The problem asks us to return true if such a repeated pattern exists anywhere in the array, otherwise return false.

The constraints are very small:

  • arr.length <= 100
  • m <= 100
  • k <= 100

Because the array size is small, even moderately inefficient solutions can pass. However, we still want to write a clean and optimal solution.

One important observation is that the repeated sequence must occupy exactly m * k positions consecutively. If there are not enough remaining elements from a starting position, we can stop checking early.

There are several edge cases to keep in mind:

  • Arrays where the pattern length is 1
  • Cases where the entire array is one repeated value
  • Cases where repetition almost works but breaks near the end
  • Cases where m * k > len(arr), which makes a valid pattern impossible immediately
  • Overlapping-looking patterns that are not actually consecutive repetitions

Approaches

Brute Force Approach

The brute force solution tries every possible starting index in the array. For each starting index, it extracts a candidate pattern of length m, then checks whether the next k - 1 segments of length m are identical to that pattern.

For example:

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

Starting at index 0, the candidate pattern is:

[1,2]

We then compare:

arr[2:4] == [1,2]
arr[4:6] == [1,2]

If all comparisons match, we return true.

This approach is correct because it explicitly validates every possible repeated pattern. However, it repeatedly compares entire subarrays, which introduces unnecessary work.

Optimal Approach

The key observation is that consecutive repeated blocks of length m imply:

arr[i] == arr[i + m]

for every matching position inside the repeated structure.

Instead of repeatedly slicing and comparing whole subarrays, we can compare elements directly.

We scan the array and count how many consecutive positions satisfy:

arr[i] == arr[i + m]

Every successful comparison means the pattern continues for one more matching element.

If we accumulate m * (k - 1) consecutive successful matches, then we have found a pattern of length m repeated k times.

This works because:

  • A repeated block of size m
  • Repeated k times
  • Requires exactly m * (k - 1) matching offset comparisons

This solution is simpler and more efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * k) O(1) Explicitly compares every repeated block
Optimal O(n) O(1) Uses offset comparisons to detect repetition

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize a counter called matched to 0.

This counter tracks how many consecutive positions satisfy:

arr[i] == arr[i + m]
  1. Iterate through the array from index 0 to len(arr) - m - 1.

We stop at len(arr) - m - 1 because we compare arr[i] with arr[i + m]. 3. For each index i, compare:

arr[i] == arr[i + m]
  1. If the values match:
  • Increment matched by 1
  • This means the repeated pattern continues
  1. If the values do not match:
  • Reset matched to 0
  • The consecutive repetition has been broken
  1. After updating matched, check whether:
matched == m * (k - 1)

If true, we have found enough consecutive matching positions to confirm a pattern repeated k times. 7. Return true immediately if such a pattern is found. 8. If the loop finishes without success, return false.

Why it works

If a pattern of length m repeats consecutively k times, then every element in one block must equal the corresponding element in the next block.

That means:

arr[i] == arr[i + m]

must hold for all positions inside the repeated region.

A total of k repeated blocks creates exactly m * (k - 1) required matching comparisons. Therefore, once we observe that many consecutive matches, we know a valid repeated pattern exists.

Python Solution

from typing import List

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        matched = 0

        for i in range(len(arr) - m):
            if arr[i] == arr[i + m]:
                matched += 1
            else:
                matched = 0

            if matched == m * (k - 1):
                return True

        return False

The implementation follows the optimal algorithm directly.

The variable matched stores how many consecutive offset matches we have seen so far. Each successful comparison between arr[i] and arr[i + m] means the repeated structure continues one more step.

When a mismatch occurs, the repetition chain is broken, so we reset matched back to 0.

The condition:

matched == m * (k - 1)

detects when we have accumulated enough consecutive matches to guarantee a valid repeated pattern.

The solution uses constant extra memory and scans the array only once.

Go Solution

func containsPattern(arr []int, m int, k int) bool {
    matched := 0

    for i := 0; i < len(arr)-m; i++ {
        if arr[i] == arr[i+m] {
            matched++
        } else {
            matched = 0
        }

        if matched == m*(k-1) {
            return true
        }
    }

    return false
}

The Go implementation mirrors the Python logic closely.

Go slices already provide efficient indexed access, so no additional data structures are needed. Integer overflow is not a concern because all constraints are very small.

The algorithm maintains the same matched counter and performs the same offset comparison strategy.

Worked Examples

Example 1

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

We need a single number repeated at least 3 times consecutively.

Required matches:

m * (k - 1) = 1 * 2 = 2
i arr[i] arr[i+m] Match? matched
0 1 2 No 0
1 2 4 No 0
2 4 4 Yes 1
3 4 4 Yes 2

Since matched == 2, return true.

Example 2

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

Required matches:

2 * (2 - 1) = 2
i arr[i] arr[i+m] Match? matched
0 1 1 Yes 1
1 2 2 Yes 2

We reached the required count, so return true.

The repeated pattern is:

[1,2][1,2]

Example 3

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

Required matches:

2 * (3 - 1) = 4
i arr[i] arr[i+m] Match? matched
0 1 1 Yes 1
1 2 2 Yes 2
2 1 1 Yes 3
3 2 3 No 0

We never reach 4, so return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array
Space O(1) Only a few integer variables are used

The algorithm performs exactly one scan of the array and each iteration does constant work. No auxiliary data structures are allocated, so the memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        matched = 0

        for i in range(len(arr) - m):
            if arr[i] == arr[i + m]:
                matched += 1
            else:
                matched = 0

            if matched == m * (k - 1):
                return True

        return False

sol = Solution()

assert sol.containsPattern([1,2,4,4,4,4], 1, 3) == True   # repeated single value
assert sol.containsPattern([1,2,1,2,1,1,1,3], 2, 2) == True   # repeated pair
assert sol.containsPattern([1,2,1,2,1,3], 2, 3) == False   # insufficient repetitions

assert sol.containsPattern([5,5,5,5], 1, 4) == True   # entire array same value
assert sol.containsPattern([1,2,3,4], 1, 2) == False   # no consecutive repetition

assert sol.containsPattern([1,1], 1, 2) == True   # smallest valid repetition
assert sol.containsPattern([1,2], 2, 2) == False   # array too short

assert sol.containsPattern([1,2,3,1,2,3], 3, 2) == True   # full repeated block
assert sol.containsPattern([1,2,3,1,2,4], 3, 2) == False   # almost repeated block

assert sol.containsPattern([7,7,7,7,7], 1, 5) == True   # long repetition
assert sol.containsPattern([1,2,1,2,1,2], 2, 3) == True   # exact repetition count

assert sol.containsPattern([1,2,3,1,2], 2, 2) == False   # incomplete second block

Test Case Summary

Test Why
[1,2,4,4,4,4], m=1, k=3 Validates repeated single element
[1,2,1,2,1,1,1,3], m=2, k=2 Standard repeated pair case
[1,2,1,2,1,3], m=2, k=3 Repetition count insufficient
[5,5,5,5], m=1, k=4 Entire array identical
[1,2,3,4], m=1, k=2 No repetition exists
[1,1], m=1, k=2 Smallest successful case
[1,2], m=2, k=2 Array too short for repetition
[1,2,3,1,2,3], m=3, k=2 Full block repetition
[1,2,3,1,2,4], m=3, k=2 Near match but fails
[7,7,7,7,7], m=1, k=5 Large consecutive repetition
[1,2,1,2,1,2], m=2, k=3 Exact repetition count
[1,2,3,1,2], m=2, k=2 Incomplete repeated block

Edge Cases

Pattern Length Equals 1

When m = 1, the problem reduces to checking whether the same value appears consecutively at least k times.

For example:

[4,4,4,4]

with k = 3.

A buggy implementation might overcomplicate this case or mishandle counting. Our solution naturally handles it because comparisons become:

arr[i] == arr[i + 1]

which correctly tracks consecutive equal values.

Array Too Short for Repetition

If:

m * k > len(arr)

then it is impossible for a valid repeated pattern to exist.

For example:

arr = [1,2]
m = 2
k = 2

We would need four elements total, but only have two.

Our implementation handles this automatically because the required number of consecutive matches can never be reached.

Partial Match That Breaks Late

Consider:

[1,2,1,2,1,3]

with:

m = 2
k = 3

The sequence appears close to valid because the first two repetitions match. However, the final element breaks the pattern.

A naive implementation might incorrectly stop early after observing some repetition. Our solution correctly requires exactly:

m * (k - 1)

consecutive matches before returning true.

Overlapping But Invalid Patterns

Consider:

[1,1,1]
m = 2
k = 2

Although values repeat, there is no valid non-overlapping repetition of a length-2 pattern.

The required structure would need:

[1,1][1,1]

which requires four elements.

Our implementation correctly avoids false positives because the necessary number of offset matches is never achieved.