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

• Sliding Window
• Hash Map

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

JavaScript

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;
 }

TypeScript

Written by @manishh12

 function containsPattern(arr: number[], m: number, k: number): boolean {
   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;
 }

Python

Written by @manishh12

 class Solution:
     def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
         n = len(arr)
         for i in range(n - m * k + 1):
             pattern = arr[i:i + m]
             count = 1
             for j in range(i + m, n, m):
                 if arr[j:j + m] == pattern:
                     count += 1
                     if count >= k:
                         return True
                 else:
                     break
         return False

Java

Written by @manishh12

 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[] pattern = Arrays.copyOfRange(arr, i, i + m);
             int count = 1;
             for (int j = i + m; j < n; j += m) {
                 int[] subArray = Arrays.copyOfRange(arr, j, j + m);
                 if (Arrays.equals(pattern, subArray)) {
                     count++;
                     if (count >= k) return true;
                 } else {
                     break;
                 }
             }
         }
         return false;
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     bool containsPattern(vector<int>& arr, int m, int k) {
         int n = arr.size();
         for (int i

= 0; i <= n - m * k; i++) {
             vector<int> pattern(arr.begin() + i, arr.begin() + i + m);
             int count = 1;
             for (int j = i + m; j < n; j += m) {
                 vector<int> subArray(arr.begin() + j, arr.begin() + j + m);
                 if (pattern == subArray) {
                     count++;
                     if (count >= k) return true;
                 } else {
                     break;
                 }
             }
         }
         return false;
     }
 };

Complexity Analysis

• Time Complexity: $O(n \cdot m)$
• Space Complexity: $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

• LeetCode Problem: LeetCode Problem
• Solution Link: Detect Pattern Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta