Problem Description

You are given an array of positive integers arr and need to determine if there exists a pattern of length m that repeats at least k times consecutively.

A pattern is defined as a subarray (consecutive elements) that repeats multiple times in succession without any gaps or overlaps. The pattern has a specific length m and must appear consecutively at least k times.

For example:

• In array [1, 2, 1, 2, 1, 3] with m = 2 and k = 2, the pattern [1, 2] appears twice consecutively starting at index 0, so it returns true.
• In array [1, 2, 3, 1, 2] with m = 2 and k = 2, although [1, 2] appears twice, they are not consecutive (there's a 3 in between), so it returns false.

The function should return true if such a pattern exists, otherwise return false.

The key insight is that for a pattern of length m to repeat k times, we need m × k consecutive elements where each element at position i equals the element at position i - m. This means each element matches the corresponding element from the previous pattern repetition.

Intuition

The key observation is that if a pattern of length m repeats k times consecutively, then elements that are exactly m positions apart must be equal.

Think about it this way: if we have a repeating pattern like [a, b, c, a, b, c, a, b, c] where the pattern [a, b, c] (length 3) repeats 3 times, then:

• Element at index 0 (a) equals element at index 3 (a)
• Element at index 1 (b) equals element at index 4 (b)
• Element at index 2 (c) equals element at index 5 (c)
• And so on...

This means each element should match the element that's exactly m positions before it (except for the first m elements which form the initial pattern).

To detect k consecutive repetitions of a pattern of length m, we need to find (k-1) × m consecutive matches. Why (k-1) × m and not k × m? Because:

• The first occurrence of the pattern takes up m elements
• Each additional repetition requires m more matching elements
• So for k total repetitions, we need the first m elements plus (k-1) × m matching elements

We can track this by maintaining a counter that increments each time we find arr[i] == arr[i-m]. When this counter reaches (k-1) × m, we've found our pattern. If at any point arr[i] != arr[i-m], the pattern is broken and we reset the counter to 0, as we need consecutive matches for a valid repeating pattern.

Solution Approach

The implementation follows a single-pass traversal approach with early termination optimization:

1. Initial Check: First, we verify if the array has enough elements to potentially contain the pattern. If len(arr) < m * k, it's impossible to have a pattern of length m repeating k times, so we return false immediately.

2. Setting up Variables:

• cnt: A counter to track consecutive matches between elements that are m positions apart
• target = (k - 1) * m: The number of consecutive matches we need to confirm k repetitions of a pattern of length m

3. Main Traversal: Starting from index m (since we need to compare with elements m positions back), we iterate through the array:

for i in range(m, len(arr)):
    if arr[i] == arr[i - m]:
        cnt += 1
        if cnt == target:
            return True
    else:
        cnt = 0

For each element at position i:

• If arr[i] == arr[i - m]: This means the current element matches the element m positions before it, indicating the pattern might be continuing. We increment cnt.

  • If cnt reaches target, we've found (k-1) * m consecutive matches, confirming k repetitions of a pattern of length m, so we return true.

• If arr[i] != arr[i - m]: The pattern is broken at this position. We reset cnt to 0 and continue looking for a new potential pattern.

4. Final Return: If we complete the traversal without finding the required pattern, we return false.

The algorithm runs in O(n) time complexity where n is the length of the array, and uses O(1) extra space, making it highly efficient.

Example Walkthrough

Let's walk through the algorithm with a concrete example to see how it detects repeating patterns.

Example: arr = [2, 7, 2, 7, 2, 7, 5], m = 2, k = 3

We're looking for a pattern of length 2 that repeats 3 times consecutively.

Step 1: Initial Setup

• Array length: 7
• Check if possible: 7 >= 2 * 3 = 6 ✓ (enough elements)
• Initialize cnt = 0
• Calculate target = (3 - 1) * 2 = 4 (we need 4 consecutive matches)

Step 2: Traverse Starting from Index m=2

Pattern Found! The pattern [2, 7] repeats 3 times consecutively:

• First occurrence: indices 0-1: [2, 7]
• Second occurrence: indices 2-3: [2, 7]
• Third occurrence: indices 4-5: [2, 7]

Counter-Example: arr = [2, 7, 2, 5, 2, 7], m = 2, k = 3

Same setup: cnt = 0, target = 4

No Pattern Found! Although [2, 7] appears twice, the pattern breaks at index 3 where we have 5 instead of 7. The algorithm correctly returns false because we never reach the target of 4 consecutive matches.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm iterates through the array once starting from index m to the end of the array. Each iteration performs constant time operations: comparing two array elements (arr[i] == arr[i - m]), incrementing or resetting a counter, and checking if the counter equals the target value. Since we traverse the array once with constant operations per element, the overall time complexity is linear.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains three variables: cnt (counter), target (calculated as (k - 1) * m), and the loop variable i. These variables occupy constant space that doesn't scale with the input array size, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Target Calculation

Pitfall: A common mistake is incorrectly calculating how many consecutive matches are needed. Some might think we need k * m matches instead of (k - 1) * m.

Why it happens: The confusion arises from thinking about total elements versus transitions between patterns. If we have k repetitions of a pattern of length m, there are k * m total elements, but only (k - 1) * m positions where we compare elements that are m positions apart.

Example: For pattern [1, 2] repeated 3 times: [1, 2, 1, 2, 1, 2]

• Total elements: 3 × 2 = 6
• Comparisons: arr[2]==arr[0], arr[3]==arr[1], arr[4]==arr[2], arr[5]==arr[3] → 4 matches = (3-1) × 2

Solution: Remember that we're counting transitions, not total elements. The formula (k - 1) * m represents the number of "links" between k consecutive patterns.

2. Not Resetting the Counter Properly

Pitfall: Forgetting to reset the counter to 0 when a mismatch occurs, or incorrectly trying to preserve partial matches.

Wrong approach:

if arr[i] != arr[i - m]:
    consecutive_matches -= 1  # Wrong! Should reset to 0

Why it's wrong: Pattern matching requires ALL elements to match consecutively. A single mismatch means we need to start fresh. There's no concept of "partial credit" in this problem.

Solution: Always reset to 0 on mismatch. The pattern must be perfectly consecutive without any breaks.

3. Off-by-One Error in Loop Starting Point

Pitfall: Starting the loop from the wrong index, such as range(0, len(arr)) or range(m-1, len(arr)).

Why it happens: Confusion about when we can first make a comparison. We need at least m elements before we can compare with an element m positions back.

Correct approach: Start from index m because:

• At index m, we can first compare arr[m] with arr[0]
• This gives us access to elements from both the potential first and second pattern occurrences

Solution: Always start the loop at index m: for i in range(m, len(arr))

4. Incorrect Early Termination Check

Pitfall: Using the wrong condition for the array size check, such as len(arr) <= m * k or len(arr) < m + k.

Why it's wrong:

• len(arr) <= m * k would reject valid cases where length exactly equals m * k
• len(arr) < m + k uses addition instead of multiplication, which is mathematically incorrect

Solution: Use len(arr) < m * k because we need exactly m * k elements to have k complete repetitions of a pattern of length m.