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 <= 100In #1566 Detect Pattern of Length M Repeated K or More Times, the task is to determine whether a subarray of length m appears consecutively at least k times. The key observation is that repeated patterns imply elements at positions i and i + m should match for the duration of the repetition.
A straightforward approach is enumeration: iterate through possible starting indices and compare the next m elements repeatedly for k segments. If all segments match, a valid repeated pattern exists.
An optimized technique avoids rechecking entire segments by comparing elements spaced m apart. Maintain a running count whenever arr[i] == arr[i + m]. If the count reaches m * (k - 1), it indicates the pattern repeats k times consecutively.
This method scans the array once, leading to efficient performance with O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Enumeration | O(n * m * k) | O(1) |
| Optimized Pattern Comparison (m-distance check) | O(n) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Use a three-layer loop to check all possible patterns by iterating through all possible starting positions, all indexes less than m, and if the character at the index is repeated k times.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If a pattern of length m repeats consecutively, each element should match the element exactly m positions ahead. By checking arr[i] == arr[i + m], you can confirm whether the sequence continues repeating without rechecking the entire pattern each time.
Problems involving pattern detection and repeated subarrays appear in many technical interviews, including FAANG-style rounds. While this exact problem may not always appear, the underlying idea of scanning arrays and detecting repetition patterns is commonly tested.
No complex data structure is required for this problem. Since the input is already an array, a simple linear scan with index comparisons is sufficient. This keeps the solution efficient with constant extra space.
The optimal approach compares elements that are m indices apart while scanning the array. If arr[i] equals arr[i + m], you increment a counter tracking repeated matches. When the counter reaches m * (k - 1), it confirms that the pattern of length m repeats k times consecutively.