Detect Pattern of Length M Repeated K or More Times - Video Solutions
detect pattern of length m repeated k or more times | leetcode 1566
Detect Pattern of Length M Repeated K or More Times - Video Solution
Watch 10 video solutions for Detect Pattern of Length M Repeated K or More Times, a easy level problem involving Array, Enumeration. This walkthrough by Naresh Gupta has 2,327 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 100
Approach Overview
Problem 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.
Complexity Analysis
| 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 |