Detect Pattern of Length M Repeated K or More Times

Easy

Hudson River Trading

1 view

Topics:

ArraysTwo PointersSliding Windows

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

Detect Pattern of Length M Repeated K or More Times

Easy

Hudson River Trading

1 view

Topics:

ArraysTwo PointersSliding Windows

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `arr`, and the values of `m` and `k`?
Can the integers in the input array `arr` be negative, zero, or non-integer?
If multiple repeating patterns of length `m` exist with repetition count of `k` or more, should I return true as soon as I find one, or do I need to find the longest/first/last one?
Could `m` ever be zero or greater than the length of the input array `arr`?
Is a pattern allowed to overlap with itself, or must it be completely distinct? For instance, with arr = [1, 2, 1, 2, 1, 2], m = 2, and k = 2, does [1, 2, 1, 2] qualify?

Brute Force Solution

Approach

The brute force approach is like trying every single possible option to see if it works. We want to find a repeating pattern within a larger sequence, so we'll check every potential pattern and see if it repeats enough times.

Here's how the algorithm would work step-by-step:

First, pick a possible length for our repeating pattern.
Then, starting from the beginning of the sequence, grab a chunk of that length. This is our potential pattern.
Now, see if this pattern repeats right after itself. Check if the sequence immediately following our pattern is the exact same.
If it does repeat, count how many times it repeats consecutively.
If the pattern repeats enough times (our required minimum), we've found a solution!
If it doesn't repeat enough times, or doesn't repeat at all, slide our starting position forward by one and try again with the same pattern length.
Also, try different pattern lengths, repeating the process for each possible length.
If we check every possible pattern length and every starting position without finding a pattern that repeats enough, then no such pattern exists.

Code Implementation

def detect_pattern_brute_force(sequence, pattern_length, repetition_count):
    sequence_length = len(sequence)

    for i in range(1, pattern_length + 1):

        # Trying different potential pattern lengths
        for starting_index in range(sequence_length - i * repetition_count + 1):
            potential_pattern = sequence[starting_index:starting_index + i]
            repetitions = 1
            current_index = starting_index + i

            # Need to verify consecutive repetitions of pattern
            while current_index + i <= sequence_length and sequence[current_index:current_index + i] == potential_pattern:
                repetitions += 1
                current_index += i

            # Check if the pattern repeats enough times
            if repetitions >= repetition_count:
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – Let n be the length of the input array. The algorithm iterates through all possible pattern lengths from 1 to n/2 (outer loop). For each pattern length m, it iterates through all possible starting positions in the array (middle loop), which is O(n). For each starting position and pattern length, it checks if the pattern repeats at least k times, which involves comparing elements within the array and takes O(n) time in the worst case because it is bounded by the original sequence size. Therefore, the total time complexity is O(n * n * n), which simplifies to O(n^3).

Space Complexity

O(1) – The described brute force approach primarily utilizes iterative comparisons and counting. It does not explicitly mention creating any auxiliary data structures like lists, arrays, or hash maps. The algorithm only uses a few integer variables to store the length of the pattern, the starting position, and the repetition count. Therefore, the space required is constant and independent of the input sequence length N.

Optimal Solution

Approach

To efficiently find repeating patterns, we slide a window of the specified pattern length across the sequence. We count how many times this window repeats consecutively, stopping early if we don't find enough repetitions.

Here's how the algorithm would work step-by-step:

Start at the beginning of the sequence.
Consider a segment of the sequence equal to the pattern length. This is our sliding window.
Look at the sequence immediately following the window. Does it match the content of the window?
If it matches, increase the count of repetitions.
Keep comparing the window to the sequence immediately after it, increasing the count each time you find a match.
If you find that the pattern repeats the required number of times or more, you're done, return true.
If you reach a point where the sequence doesn't match the window, or you run out of sequence to check, reset the repetition count to zero and slide the window forward by one position.
Repeat steps 2-7 until you've checked all possible starting positions for the pattern within the sequence.
If you never found the required number of repetitions, return false.

Code Implementation

def detect_pattern(arr, pattern_length, repetition_count):
    array_length = len(arr)

    for start_index in range(array_length - pattern_length * repetition_count + 1):
        number_of_repeats = 0

        # Check for consecutive repetitions
        while start_index + (number_of_repeats + 1) * pattern_length <= array_length:
            
            is_match = True
            for index_in_pattern in range(pattern_length):
                if arr[start_index + index_in_pattern] != \
                   arr[start_index + (number_of_repeats + 1) * pattern_length + index_in_pattern]:
                    is_match = False
                    break

            if is_match:
                number_of_repeats += 1
            else:
                break

        # Return true if we found enough repetitions
        if number_of_repeats + 1 >= repetition_count:
            return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – The outer loop iterates through the array of size n, considering each possible starting position for the pattern. Inside the loop, we compare the pattern (of length m) with the subsequent segments of the array to check for repetitions. In the worst case, for each starting position, we might need to perform m comparisons multiple times to check for K repetitions, or until we reach the end of the array. Therefore, the time complexity is approximately O(n*m), where n is the length of the input array and m is the length of the pattern to find.

Space Complexity

O(1) – The algorithm uses a few integer variables to keep track of the current position, pattern length, and repetition count. These variables consume a constant amount of space regardless of the input sequence length (N), pattern length (M), or required repetitions (K). No auxiliary data structures like arrays, lists, or hash maps are created. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array (arr is null or empty)	Return false immediately as no pattern can exist in an empty array.
m is zero or negative	Return false, as a pattern length cannot be zero or negative.
k is zero or negative	Return false as repetition count must be a positive integer.
m is larger than the array length	Return false, as a pattern of length m cannot fit within arr.
k * m is larger than the array length	Return false, as the total length of the repeated pattern exceeds the array length.
Array contains all identical values	The algorithm should correctly detect the repeated pattern if m and k allow for it.
Integer overflow when calculating indices or lengths, especially with large arrays or values of m or k	Use appropriate data types (e.g., long in Java/C++) to prevent integer overflow issues.
Input array contains negative numbers	The algorithm must work correctly with negative numbers in the array.