Scale Engineer

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.

class Solution {    public boolean containsPattern(int[] arr, int m, int k) {        int n = arr.length;        if (m * k > n) {            return false;        }        // Iterate through all possible starting points of the pattern sequence        for (int i = 0; i <= n - m * k; i++) {            boolean allBlocksMatch = true;            // Check if the k-1 blocks following the first one match            for (int j = 1; j < k; j++) {                // Compare the first block (starting at i) with the j-th block (starting at i + j*m)                for (int offset = 0; offset < m; offset++) {                    if (arr[i + offset] != arr[i + j * m + offset]) {                        allBlocksMatch = false;                        break;                    }                }                if (!allBlocksMatch) {                    break;                }            }            if (allBlocksMatch) {                return true;            }        }        return false;    }}

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.

Solutions

class Solution {public  boolean containsPattern(int[] arr, int m, int k) {    int n = arr.length;    for (int i = 0; i <= n - m * k; ++i) {      int j = 0;      for (; j < m * k; ++j) {        if (arr[i + j] != arr[i + (j % m)]) {          break;        }      }      if (j == m * k) {        return true;      }    }    return false;  }}

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 →

Next problem