Detect Pattern of Length M Repeated K or More Times

Easy

#1441Time: O(n * m * k), where `n` is the length of `arr`. The outer loop runs up to `n - m*k` times. The nested loops run `k-1` and `m` times respectively. In the worst case, this is approximately `n * k * m` operations.Space: O(1), as we are not using any extra space that scales with the input size.1 company

Patterns

Enumeration

Data structures

Array

Companies

Hudson River Trading

Prompt

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 <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible subarray of length m to see if it forms a pattern that repeats k times consecutively. It's straightforward but involves multiple nested loops, leading to a higher time complexity.

Algorithm

Get the length of the array, n.
If m * k > n, it's impossible to find the pattern, so return false.
Iterate with an index i from 0 to n - m * k. This i is the potential start of the entire k-repetition sequence.
Inside the loop, assume a pattern is found (allBlocksMatch = true).
Start a nested loop with index j from 1 to k-1. This loop checks the k-1 subsequent blocks.
Start another nested loop with index offset from 0 to m-1. This loop compares elements within a block.
Compare arr[i + offset] (element from the first block) with arr[i + j*m + offset] (element from the j-th block).
If they are not equal, the pattern is broken. Set allBlocksMatch = false and break the inner loops.
If the loops for j and offset complete with allBlocksMatch still true, it means we have found a valid pattern. Return true.
If the outer loop for i finishes, no pattern was found. Return false.

Walkthrough

The brute-force method iterates through the array arr to find a starting point i for a potential pattern. The loop for i only needs to go up to arr.length - m * k, as any starting point beyond that cannot accommodate a pattern of length m repeated k times.

For each starting index i, we define the pattern as the subarray arr[i...i+m-1]. Then, we check the subsequent k-1 blocks of size m to see if they are identical to our initial pattern. A block is considered a match if all its m elements are equal to the corresponding elements in the pattern. If we find k-1 such consecutive matching blocks, it means the pattern is repeated k times in total, and we can return true.

If the loops complete without finding such a pattern, it means no such pattern exists, and we return false.

1class Solution {2    public boolean containsPattern(int[] arr, int m, int k) {3        int n = arr.length;4        if (m * k > n) {5            return false;6        }7        // Iterate through all possible starting points of the pattern sequence8        for (int i = 0; i <= n - m * k; i++) {9            boolean allBlocksMatch = true;10            // Check if the k-1 blocks following the first one match11            for (int j = 1; j < k; j++) {12                // Compare the first block (starting at i) with the j-th block (starting at i + j*m)13                for (int offset = 0; offset < m; offset++) {14                    if (arr[i + offset] != arr[i + j * m + offset]) {15                        allBlocksMatch = false;16                        break;17                    }18                }19                if (!allBlocksMatch) {20                    break;21                }22            }23            if (allBlocksMatch) {24                return true;25            }26        }27        return false;28    }29}

Complexity

Time

O(n * m * k), where `n` is the length of `arr`. The outer loop runs up to `n - m*k` times. The nested loops run `k-1` and `m` times respectively. In the worst case, this is approximately `n * k * m` operations.

Space

O(1), as we are not using any extra space that scales with the input size.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for the given constraints.

Cons

Inefficient due to three nested loops.
Performs many redundant comparisons.

A more efficient approach that solves the problem in a single pass through the array. It cleverly counts consecutive matching elements to identify the repeated pattern, reducing the time complexity significantly.

Algorithm

Initialize a count variable to 0. This will track the number of consecutive indices i where arr[i] matches arr[i+m].
Iterate through the array with an index i from 0 to arr.length - m - 1.
At each index i, compare arr[i] with arr[i+m].
If arr[i] == arr[i+m], increment count.
If arr[i] != arr[i+m], reset count to 0 because the consecutive match streak is broken.
After updating the count, check if count is equal to m * (k - 1).
If it is, we have found k-1 consecutive repetitions of a pattern of length m. This means we have k identical blocks in total. Return true.
If the loop completes without the condition in step 6 being met, return false.

Walkthrough

This optimized approach is based on a key observation: a pattern of length m is repeated k times consecutively if and only if there is a sequence of (k-1) * m consecutive indices where each element arr[i] is equal to the element m positions after it, arr[i+m].

Let's break this down. If we have k identical blocks of size m, say B_1, B_2, ..., B_k, then B_2 must be identical to B_1, B_3 to B_2, and so on. This chain of equalities implies that for every position in blocks B_2 through B_k, the element at that position is the same as the element m positions earlier. The total number of elements in blocks B_2 through B_k is (k-1) * m.

Therefore, we can solve the problem by iterating through the array and maintaining a count of consecutive indices i where arr[i] == arr[i+m]. If arr[i] is not equal to arr[i+m], the streak is broken, and we reset the count to zero. If the count ever reaches (k-1) * m, we have found our pattern, and we can return true.

If we finish iterating through the array without the count reaching the target value, no such pattern exists, and we return false.

1class Solution {2    public boolean containsPattern(int[] arr, int m, int k) {3        int n = arr.length;4        if (m * k > n) {5            return false;6        }7        int count = 0;8        // We check arr[i] against arr[i+m].9        // The loop runs from i=0 up to the point where i+m is a valid index.10        for (int i = 0; i + m < n; i++) {11            if (arr[i] == arr[i + m]) {12                count++;13            } else {14                count = 0;15            }16            // A pattern is formed by k blocks. This means k-1 repetitions.17            // Each repetition means a block of size m matches the previous one.18            // This requires m consecutive matches of arr[i] == arr[i+m].19            // So, for k-1 repetitions, we need (k-1)*m such consecutive matches.20            if (count == m * (k - 1)) {21                return true;22            }23        }24        return false;25    }26}

Complexity

Time

O(n), where `n` is the length of `arr`. We iterate through the array a single time.

Space

O(1), as we only use a single integer variable (`count`) for tracking.

Trade-offs

Pros

Highly efficient with linear time complexity.
Uses constant extra space.
Avoids redundant work by checking relationships between elements m distance apart.

Cons

The logic might be slightly less intuitive to grasp initially compared to the direct brute-force approach.

Solutions

Solution

1class Solution {2public3  boolean containsPattern(int[] arr, int m, int k) {4    int n = arr.length;5    for (int i = 0; i <= n - m * k; ++i) {6      int j = 0;7      for (; j < m * k; ++j) {8        if (arr[i + j] != arr[i + (j % m)]) {9          break;10        }11      }12      if (j == m * k) {13        return true;14      }15    }16    return false;17  }18}

1class Solution:2    def containsPattern(self, arr: List[int], m: int, k: int) -> bool: n = len(arr) for i in range(n - m * k + 1): j = 0 while j < m * k: if arr[i + j] != arr[i + (j % m)]: break j += 1 if j == m * k: return True return False

1class Solution {2public:3  bool containsPattern(vector<int> &arr, int m, int k) {4    int n = arr.size();5    for (int i = 0; i <= n - m * k; ++i) {6      int j = 0;7      for (; j < m * k; ++j) {8        if (arr[i + j] != arr[i + (j % m)]) {9          break;10        }11      }12      if (j == m * k) {13        return true;14      }15    }16    return false;17  }18};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem