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

EasyArrayEnumeration
Leetcode Link

Problem Description

In this problem, we are given an array of positive integers arr. Our task is to determine if there exists a subarray (a consecutive sequence of elements) of a certain length m that appears at least k times in the array, one immediately after the other (consecutively and without overlapping). The repeated subarrays represent the 'pattern' we are looking for.

For example, if the array is [1, 2, 1, 2, 1, 2, 1, 3] and m = 2, k = 3, the pattern [1, 2] appears three times consecutively without overlapping, so the answer would be true.

The problem asks us to return true if such a pattern exists and false if it does not.

Intuition

The straightforward way to solve this problem is to check each possible subarray of length m to see if it is followed by itself k-1 more times. This approach requires us to iterate through the given array and attempt to match every sequence of length m followed by k-1 identical sequences.

Specifically, we:

  1. Iterate over the array from the start up to the point where there is still room for m*k elements (inclusive), since we need at least that many elements for a valid pattern to exist.

  2. For each start position i, we check the following m*k elements to see if the sequence repeats k times. We compare each element in this window to the corresponding element in the first m elements. If all these elements match as required, it means we have found our pattern, and we can return true.

  3. If, after checking all possible starting points, we haven't returned true, it means no such pattern exists, and we return false.

This solution approach is clever because it capitalizes on the repetitive nature of the problem, allowing us to do pattern matching across different segments of the array using a sliding window concept. The window sizes and positions are calculated systematically to cover all potential pattern locations without missing any possibilities or checking any region of the array unnecessarily.

Solution Approach

The implementation of the solution follows a simple but effective algorithm, utilizing basic iteration and comparison without requiring sophisticated data structures or patterns beyond array manipulation and the concept of a sliding window.

Here are the steps the algorithm uses:

  1. Calculate the length of the array n.
  2. Start iterating through the array with the variable i, which indicates the starting index of the current window. The loop's ending condition ensures that we don't check patterns starting in places where there wouldn't be enough room left in the array for m * k elements, hence i stops at n - m * k + 1.
  3. Initialize the inner loop with the variable j to zero. This inner loop will step through the elements in the current window, checking if the pattern is repeated k times.

The following pseudocode outlines the iteration process:

1for i from 0 to (n - m * k + 1):
2  set j to 0
3  while j < m * k:
4    if arr[i + j] != arr[i + (j % m)]:
5      break out of the while-loop
6    increment j
7  if j == m * k:
8    return True

Explanation of crucial parts of the above pseudocode:

  • for i from 0 to (n - m * k + 1): It ensures that we do not start a pattern check where the remaining elements in the array are fewer than needed to make k repetitions of length m.
  • while j < m * k: It's essential to check m * k elements for consecutive repetition.
  • if arr[i + j] != arr[i + (j % m)]: This comparison is vital for the algorithm. The index i + j represents the current element we are checking, while i + (j % m) gives us the corresponding index in the original m length pattern with which we are comparing. If a mismatch is found, we break out of the inner loop, as the current starting index i cannot be the start of a valid pattern.
  • if j == m * k: After the inner loop terminates, if j, the count of consecutive matches, equals m * k, it means we have found a pattern repeated k times. Hence, we return True.

If the main loop terminates without returning True, no pattern of length m repeated k times has been found, so the solution returns False.

This approach effectively employs a brute-force mechanism to check for the pattern in all possible places by using a nested loop where the inner loop validates the repetitiveness of the pattern while the outer loop shifts the starting position of the check.

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we have the array arr = [4, 5, 4, 5, 4, 5, 6], and we want to check if there's a subarray of length m = 2 that repeats k = 3 times.

Step-by-step:

  1. We start by calculating the length of the array n, which is 7 in this case.

  2. We begin iterating through the array, starting at index i = 0. The outer loop will only go up to index i = 7 - (2 * 3) + 1 = 3 to ensure there's enough room for a subarray of length m repeated k times.

  3. With each i, we have:

    • At i = 0: We check if [4, 5] repeats 3 times. The inner loop will check the elements following the index i to see if they match the initial subarray [4, 5]. We check arr[0] with arr[0 + 0 % 2] and arr[1] with arr[0 + 1 % 2], then arr[2] with arr[0 + 2 % 2] and arr[3] with arr[0 + 3 % 2], and so on until we have checked 2 * 3 = 6 elements for consecutiveness. Since the pattern [4, 5] repeats for the required 3 times, j will equal 6 at the end of the while-loop, and we will return True.
  4. Since we found a valid pattern starting at i = 0, there is no need to continue with further iterations.

Thus, for the given array arr, the function will return True.

This example demonstrates the simplicity and effectiveness of the brute force solution approach in finding whether the array contains a subarray that repeats consecutively k times.

Python Solution

1from typing import List
2
3class Solution:
4    def contains_pattern(self, array: List[int], pattern_length: int, repetitions: int) -> bool:
5        # Calculate the size of the array
6        array_length = len(array)
7      
8        # Loop over the array up to the point where the pattern can possibly fit
9        for start_index in range(array_length - pattern_length * repetitions + 1):
10            # Initialize a pointer to traverse the pattern
11            pattern_index = 0
12          
13            # Keep traversing while the pattern matches the subsequent blocks of the same size
14            while pattern_index < pattern_length * repetitions:
15                # If an element does not match its corresponding element in the first block, break
16                if array[start_index + pattern_index] != array[start_index + (pattern_index % pattern_length)]:
17                    break
18                # Move to the next element in the pattern
19                pattern_index += 1
20
21            # If we have traversed the entire pattern without a break, the pattern is present
22            if pattern_index == pattern_length * repetitions:
23                return True
24      
25        # If we exit the loop without returning True, the pattern is not present
26        return False
27

Java Solution

1class Solution {
2
3    // Function to check if the array contains a repeated pattern of length m, repeated k times.
4    public boolean containsPattern(int[] arr, int m, int k) {
5        // Find the length of the array.
6        int n = arr.length;
7      
8        // Loop through the array up to the point where the pattern could fit.
9        for (int i = 0; i <= n - m * k; ++i) {
10          
11            // Initialize 'j' which will iterate over the length of the pattern times 'k'.
12            int j = 0;
13            for (; j < m * k; ++j) {
14              
15                // Check if the current element doesn't match with the corresponding element in the pattern.
16                // The modulo operation finds the corresponding position in the pattern.
17                if (arr[i + j] != arr[i + (j % m)]) {
18                    break; // If any element doesn't match, break the loop.
19                }
20            }
21          
22            // If 'j' runs through the full pattern without breaking, the pattern exists in the array.
23            if (j == m * k) {
24                return true;
25            }
26        }
27      
28        // If we traverse the entire array without returning true, the pattern does not exist.
29        return false;
30    }
31}
32

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    bool containsPattern(std::vector<int>& arr, int m, int k) {
6        int size = arr.size();
7        // Loop through the array, but only up to the point where we can fit m * k elements
8        for (int i = 0; i <= size - m * k; ++i) {
9            int patternLength = 0;
10            // Try to match a pattern of length m, repeated k times
11            for (; patternLength < m * k; ++patternLength) {
12                // The index for pattern comparison is the current index i
13                // plus the current patternLength, but wrapped by m
14                // to restart comparison every m elements
15                if (arr[i + patternLength] != arr[i + (patternLength % m)]) {
16                    break; // Pattern does not match, break and move to next starting index
17                }
18            }
19            // If we matched a full pattern (m*k elements)
20            if (patternLength == m * k) {
21                return true; // A repeat pattern of length m, repeated k times is found
22            }
23        }
24        // After checking the entire array, no pattern was found
25        return false;
26    }
27};
28

Typescript Solution

1function containsPattern(arr: number[], m: number, k: number): boolean {
2    // Get the length of the array.
3    const arrayLength = arr.length;
4
5    // Loop through the array, but only up to the point where a pattern of length m repeated k times could fit.
6    for (let startIndex = 0; startIndex <= arrayLength - m * k; ++startIndex) {
7        let patternIndex;
8
9        // Check if the pattern repeats k times from the current starting index.
10        for (patternIndex = 0; patternIndex < m * k; ++patternIndex) {
11            // The pattern breaks if the current element does not match the corresponding element in the pattern.
12            if (arr[startIndex + patternIndex] !== arr[startIndex + (patternIndex % m)]) {
13                break;
14            }
15        }
16
17        // If the loop completed, the pattern was found repeated k times.
18        if (patternIndex === m * k) {
19            return true;
20        }
21    }
22
23    // If no matching pattern repetition was found, return false.
24    return false;
25}
26

Time and Space Complexity

Time Complexity

The main operation of the algorithm is a nested loop where the outer loop runs n - m * k + 1 times. The inner loop runs up to m * k times, but often breaks earlier if the pattern condition is not met.

The worst-case scenario occurs when arr[i + j] == arr[i + (j % m)] for each i and j until the last iteration, which means that even though we do not have a complete pattern, each partial comparison is true. If we assume the worst-case, the inner loop would run m * k for each of the n - m * k + 1 iterations.

As a result, the time complexity in the worst case is O((n - m * k + 1) * m * k), which simplifies to O(n * m * k).

Space Complexity

The algorithm uses a fixed amount of space, with only simple variables defined and no use of any data structures that grow with the input size.

Therefore, the space complexity is O(1).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫