Detect Pattern of Length M Repeated K or More Times

Detect Pattern of Length M Repeated K or More Times - Problem

Array Enumeration Easy

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.

Input & Output

Example 1 — Basic Pattern Found

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

› Output: true

💡 Note: Pattern [4] of length 1 repeats 4 times starting at index 2, which is ≥ 3 repetitions required

Example 2 — Pattern Too Short

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

› Output: true

💡 Note: Pattern [1,2] of length 2 repeats exactly 2 times starting at index 0: [1,2,1,2]

Example 3 — No Pattern Found

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

› Output: false

💡 Note: No pattern of length 2 repeats 3 or more times. Array length 5 < 2×3=6 required

Constraints

2 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ 100
1 ≤ m ≤ 100
2 ≤ k ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array with potential repeated patterns and parameters m, k

Pattern Search

Check each position for patterns of length m repeated k+ times

Result

Return true if any valid pattern found

Key Takeaway

🎯 Key Insight: Check each starting position and count consecutive pattern repetitions until the required threshold k is reached

Asked in

G Google 25 f Facebook 20

The key insight is to check each possible starting position for patterns of length m and count consecutive repetitions. The brute force approach directly compares array slices, while string matching converts to strings for pattern detection. Best approach is brute force with Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Pattern Matching	O(n × m)	O(1)	Check every possible starting position for patterns of length m
String Pattern Matching	O(n × m)	O(n × m)	Convert array to string and use string pattern matching techniques

Brute Force Pattern Matching — Algorithm Steps

Iterate through each possible starting position
Extract pattern of length m
Count consecutive repetitions of this pattern
Return true if repetitions >= k

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Pattern

Take m elements as pattern from current position

Count Repetitions

Check how many times pattern repeats consecutively

Check Threshold

Return true if repetitions >= k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool patternMatch(int* arr, int start1, int start2, int len) {
    for (int i = 0; i < len; i++) {
        if (arr[start1 + i] != arr[start2 + i]) {
            return false;
        }
    }
    return true;
}

bool solution(int* arr, int arrSize, int m, int k) {
    if (m * k > arrSize) {
        return false;
    }
    
    for (int i = 0; i <= arrSize - m * k; i++) {
        int count = 1;
        int j = i + m;
        
        while (j + m <= arrSize && patternMatch(arr, i, j, m)) {
            count++;
            j += m;
        }
        
        if (count >= k) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int m, k;
    scanf("%d", &m);
    scanf("%d", &k);
    
    bool result = solution(arr, arrSize, m, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of n positions, we compare patterns of length m

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Pattern Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler