Skip to main content

Detect Pattern Solution

In this page, we will solve the Detect Pattern problem using multiple approaches. We will provide the implementation of the solution in Python, JavaScript, TypeScript, Java, and C++.

Problem Description​

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 elements) that occurs k or more times within the array arr.

The pattern can be of any length and must not overlap.

Examples​

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The repeated pattern is [4].

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The repeated pattern is [1,2].

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: There is no such pattern.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: There is no such pattern.

Constraints​

  • 2<=arr.length<=1002 <= arr.length <= 100
  • 1<=arr[i]<=1001 <= arr[i] <= 100
  • 1<=m<=1001 <= m <= 100
  • 2<=k<=1002 <= k <= 100

Solution for Detect Pattern Problem​

Intuition and Approach​

We can solve this problem using a sliding window approach. We iterate through the array and check if there is a pattern of length m that repeats k or more times.

Approach: Sliding Window​

In this approach, we use a sliding window of length m to check for repeated patterns.

Implementation​

Live Editor
function detectPattern() {
  const arr = [1, 2, 4, 4, 4, 4];
  const m = 1;
  const k = 3;

  const containsPattern = function(arr, m, k) {
    const n = arr.length;
    for (let i = 0; i <= n - m * k; i++) {
      let pattern = arr.slice(i, i + m);
      let count = 1;
      for (let j = i + m; j < n; j += m) {
        if (arr.slice(j, j + m).toString() === pattern.toString()) {
          count++;
          if (count >= k) return true;
        } else {
          break;
        }
      }
    }
    return false;
  };

  const result = containsPattern(arr, m, k);
  return (
    <div>
      <p>
        <b>Input:</b> arr = {JSON.stringify(arr)}, m = {m}, k = {k}
      </p>
      <p>
        <b>Output:</b> {result ? "true" : "false"}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages​

Written by @manishh12
 function containsPattern(arr, m, k) {
const n = arr.length;
for (let i = 0; i <= n - m * k; i++) {
let pattern = arr.slice(i, i + m);
let count = 1;
for (let j = i + m; j < n; j += m) {
if (arr.slice(j, j + m).toString() === pattern.toString()) {
count++;
if (count >= k) return true;
} else {
break;
}
}
}
return false;
}

Complexity Analysis​

  • Time Complexity: O(nâ‹…m)O(n \cdot m)
  • Space Complexity: O(1)O(1)
  • Where n is the length of the array arr and m is the length of the pattern.
  • We iterate through the array once and compare patterns of length m.
  • The space complexity is constant as we use only a few variables irrespective of the size of the input.
Note

By using these approaches, we can efficiently solve the Detect Pattern problem for the given constraints.

References​