algoadvance

Leetcode 1566. Detect Pattern of Length M Repeated K or More Times

Problem Statement

Given an array of positive integers arr, you need to check if there exists a pattern of length m that repeats at least k times consecutively.

Formally, a pattern is a subarray of length m that is repeated k times consecutively without overlapping. More specifically, for an index i, the pattern is arr[i], arr[i+1], ..., arr[i+m-1]. You need to check whether this subarray appears at least k times consecutively such that the overall length of this repeating pattern is m*k.

Clarifying Questions

  1. What is the minimum length of arr?
    • The array length should be at least 1.
  2. Is m always less than or equal to the length of arr?
    • Yes.
  3. Can k be 1?
    • Yes, if k=1, we are looking for any subarray of length m.
  4. Can the elements of arr be any positive integer?
    • Yes, they are all positive integers.
  5. What should be returned if there are multiple patterns that meet the criteria?
    • Just returning true if any such pattern exists is sufficient.

Strategy

To solve this problem, we can implement the following approach:

  1. Iterate through the array from the start to the point where the remaining length of the array is at least m*k.
  2. For each starting index, check the subarray from that index till the next m*k positions.
  3. Within this range, check if the subarray of length m is consecutively repeating k times.

Code

#include <vector>
using namespace std;

bool containsPattern(vector<int>& arr, int m, int k) {
    int n = arr.size();
    
    for (int i = 0; i <= n - m * k; ++i) {
        bool isPattern = true;
        for (int j = 0; j < m * k; ++j) {
            if (arr[i + j] != arr[i + (j % m)]) {
                isPattern = false;
                break;
            }
        }
        if (isPattern) {
            return true;
        }
    }
    return false;
}

Explanation of Code

  1. Initialization: We start by determining the size of the array n.
  2. Outer Loop: This loop iterates from the start of the array up to the point where checking a subarray of length m * k makes sense (i <= n - m * k).
  3. Inner Loop: This loop checks if each element in the subarray of length m * k matches its corresponding element in the repeating pattern.
  4. Condition Check: If at any point the subarray does not match the pattern, we break out of the inner loop. If the entire subarray matches, we return true.
  5. Return: If no matching subarray is found, we return false.

Time Complexity

Therefore, the overall complexity is still manageable within the constraints typically given for such problems (assuming n is reasonably large but not excessively so).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI