1566. Detect Pattern of Length M Repeated K or More Times
Problem Description
In this problem, we are given an array of positive integers arr
. Our task is to determine if there exists a subarray (a consecutive sequence of elements) of a certain length m
that appears at least k
times in the array, one immediately after the other (consecutively and without overlapping). The repeated subarrays represent the 'pattern' we are looking for.
For example, if the array is [1, 2, 1, 2, 1, 2, 1, 3]
and m = 2
, k = 3
, the pattern [1, 2]
appears three times consecutively without overlapping, so the answer would be true
.
The problem asks us to return true
if such a pattern exists and false
if it does not.
Intuition
The straightforward way to solve this problem is to check each possible subarray of length m
to see if it is followed by itself k-1
more times. This approach requires us to iterate through the given array and attempt to match every sequence of length m
followed by k-1
identical sequences.
Specifically, we:
-
Iterate over the array from the start up to the point where there is still room for
m*k
elements (inclusive), since we need at least that many elements for a valid pattern to exist. -
For each start position
i
, we check the followingm*k
elements to see if the sequence repeatsk
times. We compare each element in this window to the corresponding element in the firstm
elements. If all these elements match as required, it means we have found our pattern, and we can returntrue
. -
If, after checking all possible starting points, we haven't returned
true
, it means no such pattern exists, and we returnfalse
.
This solution approach is clever because it capitalizes on the repetitive nature of the problem, allowing us to do pattern matching across different segments of the array using a sliding window concept. The window sizes and positions are calculated systematically to cover all potential pattern locations without missing any possibilities or checking any region of the array unnecessarily.
Solution Approach
The implementation of the solution follows a simple but effective algorithm, utilizing basic iteration and comparison without requiring sophisticated data structures or patterns beyond array manipulation and the concept of a sliding window.
Here are the steps the algorithm uses:
- Calculate the length of the array
n
. - Start iterating through the array with the variable
i
, which indicates the starting index of the current window. The loop's ending condition ensures that we don't check patterns starting in places where there wouldn't be enough room left in the array form * k
elements, hencei
stops atn - m * k + 1
. - Initialize the inner loop with the variable
j
to zero. This inner loop will step through the elements in the current window, checking if the pattern is repeatedk
times.
The following pseudocode outlines the iteration process:
for i from 0 to (n - m * k + 1): set j to 0 while j < m * k: if arr[i + j] != arr[i + (j % m)]: break out of the while-loop increment j if j == m * k: return True
Explanation of crucial parts of the above pseudocode:
for i from 0 to (n - m * k + 1)
: It ensures that we do not start a pattern check where the remaining elements in the array are fewer than needed to makek
repetitions of lengthm
.while j < m * k
: It's essential to checkm * k
elements for consecutive repetition.if arr[i + j] != arr[i + (j % m)]
: This comparison is vital for the algorithm. The indexi + j
represents the current element we are checking, whilei + (j % m)
gives us the corresponding index in the originalm
length pattern with which we are comparing. If a mismatch is found, we break out of the inner loop, as the current starting indexi
cannot be the start of a valid pattern.if j == m * k
: After the inner loop terminates, ifj
, the count of consecutive matches, equalsm * k
, it means we have found a pattern repeatedk
times. Hence, we returnTrue
.
If the main loop terminates without returning True
, no pattern of length m
repeated k
times has been found, so the solution returns False
.
This approach effectively employs a brute-force mechanism to check for the pattern in all possible places by using a nested loop where the inner loop validates the repetitiveness of the pattern while the outer loop shifts the starting position of the check.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Suppose we have the array arr = [4, 5, 4, 5, 4, 5, 6]
, and we want to check if there's a subarray of length m = 2
that repeats k = 3
times.
Step-by-step:
-
We start by calculating the length of the array
n
, which is7
in this case. -
We begin iterating through the array, starting at index
i = 0
. The outer loop will only go up to indexi = 7 - (2 * 3) + 1 = 3
to ensure there's enough room for a subarray of lengthm
repeatedk
times. -
With each
i
, we have:- At
i = 0
: We check if[4, 5]
repeats3
times. The inner loop will check the elements following the indexi
to see if they match the initial subarray[4, 5]
. We checkarr[0]
witharr[0 + 0 % 2]
andarr[1]
witharr[0 + 1 % 2]
, thenarr[2]
witharr[0 + 2 % 2]
andarr[3]
witharr[0 + 3 % 2]
, and so on until we have checked2 * 3 = 6
elements for consecutiveness. Since the pattern[4, 5]
repeats for the required3
times,j
will equal6
at the end of the while-loop, and we will returnTrue
.
- At
-
Since we found a valid pattern starting at
i = 0
, there is no need to continue with further iterations.
Thus, for the given array arr
, the function will return True
.
This example demonstrates the simplicity and effectiveness of the brute force solution approach in finding whether the array contains a subarray that repeats consecutively k
times.
Solution Implementation
1from typing import List
2
3class Solution:
4 def contains_pattern(self, array: List[int], pattern_length: int, repetitions: int) -> bool:
5 # Calculate the size of the array
6 array_length = len(array)
7
8 # Loop over the array up to the point where the pattern can possibly fit
9 for start_index in range(array_length - pattern_length * repetitions + 1):
10 # Initialize a pointer to traverse the pattern
11 pattern_index = 0
12
13 # Keep traversing while the pattern matches the subsequent blocks of the same size
14 while pattern_index < pattern_length * repetitions:
15 # If an element does not match its corresponding element in the first block, break
16 if array[start_index + pattern_index] != array[start_index + (pattern_index % pattern_length)]:
17 break
18 # Move to the next element in the pattern
19 pattern_index += 1
20
21 # If we have traversed the entire pattern without a break, the pattern is present
22 if pattern_index == pattern_length * repetitions:
23 return True
24
25 # If we exit the loop without returning True, the pattern is not present
26 return False
27
1class Solution {
2
3 // Function to check if the array contains a repeated pattern of length m, repeated k times.
4 public boolean containsPattern(int[] arr, int m, int k) {
5 // Find the length of the array.
6 int n = arr.length;
7
8 // Loop through the array up to the point where the pattern could fit.
9 for (int i = 0; i <= n - m * k; ++i) {
10
11 // Initialize 'j' which will iterate over the length of the pattern times 'k'.
12 int j = 0;
13 for (; j < m * k; ++j) {
14
15 // Check if the current element doesn't match with the corresponding element in the pattern.
16 // The modulo operation finds the corresponding position in the pattern.
17 if (arr[i + j] != arr[i + (j % m)]) {
18 break; // If any element doesn't match, break the loop.
19 }
20 }
21
22 // If 'j' runs through the full pattern without breaking, the pattern exists in the array.
23 if (j == m * k) {
24 return true;
25 }
26 }
27
28 // If we traverse the entire array without returning true, the pattern does not exist.
29 return false;
30 }
31}
32
1#include <vector>
2
3class Solution {
4public:
5 bool containsPattern(std::vector<int>& arr, int m, int k) {
6 int size = arr.size();
7 // Loop through the array, but only up to the point where we can fit m * k elements
8 for (int i = 0; i <= size - m * k; ++i) {
9 int patternLength = 0;
10 // Try to match a pattern of length m, repeated k times
11 for (; patternLength < m * k; ++patternLength) {
12 // The index for pattern comparison is the current index i
13 // plus the current patternLength, but wrapped by m
14 // to restart comparison every m elements
15 if (arr[i + patternLength] != arr[i + (patternLength % m)]) {
16 break; // Pattern does not match, break and move to next starting index
17 }
18 }
19 // If we matched a full pattern (m*k elements)
20 if (patternLength == m * k) {
21 return true; // A repeat pattern of length m, repeated k times is found
22 }
23 }
24 // After checking the entire array, no pattern was found
25 return false;
26 }
27};
28
1function containsPattern(arr: number[], m: number, k: number): boolean {
2 // Get the length of the array.
3 const arrayLength = arr.length;
4
5 // Loop through the array, but only up to the point where a pattern of length m repeated k times could fit.
6 for (let startIndex = 0; startIndex <= arrayLength - m * k; ++startIndex) {
7 let patternIndex;
8
9 // Check if the pattern repeats k times from the current starting index.
10 for (patternIndex = 0; patternIndex < m * k; ++patternIndex) {
11 // The pattern breaks if the current element does not match the corresponding element in the pattern.
12 if (arr[startIndex + patternIndex] !== arr[startIndex + (patternIndex % m)]) {
13 break;
14 }
15 }
16
17 // If the loop completed, the pattern was found repeated k times.
18 if (patternIndex === m * k) {
19 return true;
20 }
21 }
22
23 // If no matching pattern repetition was found, return false.
24 return false;
25}
26
Time and Space Complexity
Time Complexity
The main operation of the algorithm is a nested loop where the outer loop runs n - m * k + 1
times. The inner loop runs up to m * k
times, but often breaks earlier if the pattern condition is not met.
The worst-case scenario occurs when arr[i + j] == arr[i + (j % m)]
for each i
and j
until the last iteration, which means that even though we do not have a complete pattern, each partial comparison is true. If we assume the worst-case, the inner loop would run m * k
for each of the n - m * k + 1
iterations.
As a result, the time complexity in the worst case is O((n - m * k + 1) * m * k)
, which simplifies to O(n * m * k)
.
Space Complexity
The algorithm uses a fixed amount of space, with only simple variables defined and no use of any data structures that grow with the input size.
Therefore, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!