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.
Example 1:
Input: arr = [1,2,4,4,4,4], m = 1, k = 3 Output: true Explanation: 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 Explanation: 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 Explanation: 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 <= 1001 <= arr[i] <= 1001 <= m <= 1002 <= k <= 100Problem Overview: Given an integer array arr, determine whether a pattern of length m appears consecutively at least k times. The pattern must repeat back‑to‑back without gaps. Your job is to scan the array and confirm whether such a repeating block exists.
Approach 1: Sliding Window Approach (O(n * m * k) time, O(1) space)
Iterate through every possible starting index of the array where a pattern of length m * k could fit. Treat the first m elements as the base pattern. Then compare the next m elements with that base pattern, repeating this comparison k-1 times. If all segments match, you found a valid repeating pattern. This method uses straightforward comparisons and works well for small inputs. It relies purely on sequential checks over the array and direct element comparisons.
Approach 2: Pattern Matching by Modulo (O(n) time, O(1) space)
Instead of explicitly comparing entire blocks, compare each element with the element m positions ahead. If arr[i] == arr[i + m], it means the pattern continues. Maintain a counter of consecutive matches. Every time this equality holds, increment the counter; otherwise reset it. Once the counter reaches m * (k - 1), you have verified that the pattern of length m repeats k times consecutively. This transforms the repeated pattern check into a linear scan, making it optimal. The approach uses simple enumeration while comparing elements at a fixed offset.
Recommended for interviews: The modulo comparison approach is typically expected. It reduces nested comparisons into a single pass and achieves O(n) time with constant space. The sliding window method still demonstrates understanding of pattern verification and brute-force reasoning, but the optimized approach shows stronger algorithmic insight.
This approach uses a sliding window of size m to check for repetitions. We slide this window along the array to take `m` length chunks and check if these chunks repeat `k` times consecutively.
The C code checks if there exists a subarray of length `m` that is repeated `k` times or more. It iterates over the array with a loop to check each possible starting position for such a repetition. For each position, it checks if the subsequent elements form the required repetition. If so, it returns true; otherwise, it continues until the end of the array.
Time Complexity: O(n*m*k) where n is the length of the array.
Space Complexity: O(1) since we use constant space.
This approach is based on exploiting the modulo operation to compare segments of the array directly. For each starting index, compare elements on a modulo basis within the allowed bounds.
In this C implementation, instead of checking the entire `m*k` length, the modulo approach ensures elements in offset positions match within the contiguous blocks by comparing elements modulo `m`.
Time Complexity: O(n*m) with n as the length of the array.
Space Complexity: O(1) which remains constant.
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 false.
Next, we define a variable cnt to record the current count of consecutive repetitions. If there are (k - 1) times m consecutive elements a_i in the array such that a_i = a_{i - m}, then we have found a pattern of length m that repeats at least k times, and we return true. Otherwise, we reset cnt to 0 and continue traversing the array.
Finally, if we finish traversing the array without finding a pattern that meets the conditions, we return false.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n*m*k) where n is the length of the array. |
| Pattern Matching by Modulo | Time Complexity: O(n*m) with n as the length of the array. |
| Single Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Pattern Check | O(n * m * k) | O(1) | When starting with a direct brute-force comparison or explaining the problem step-by-step in interviews |
| Modulo Pattern Matching | O(n) | O(1) | Best general solution for large arrays; avoids repeated block comparisons |
detect pattern of length m repeated k or more times | leetcode 1566 • Naresh Gupta • 2,301 views views
Watch 9 more video solutions →Practice Detect Pattern of Length M Repeated K or More Times with our built-in code editor and test cases.
Practice on FleetCode