algoadvance

Given an array of positive integers arr, find a pattern of length m that is repeated at least k times in the array. The pattern must be consecutive, which means that between consecutive appearances of the same pattern, there cannot be any other elements.

Clarifying Questions

1. Input constraints:
   • What are the minimum and maximum values for m and k?
   • Can arr be empty or have very few elements?
2. Expected output:
   • Should the function return a boolean indicating if the pattern exists or not?
   • Should any other information be returned?

Let’s assume:

• The minimal length of m and k is 1.
• The array is not empty and contains at least one element.
• The function should return a boolean indicating if there exists a repeated pattern of length m repeated at least k times consecutively.

Code

def contains_pattern(arr, m, k):
    n = len(arr)
    
    for i in range(n - m * k + 1):
        pattern = arr[i:i + m]
        matches = 0
        
        for j in range(i, n - m + 1, m):
            if arr[j:j + m] == pattern:
                matches += 1
            else:
                break
            
            if matches == k:
                return True
                
    return False

Strategy

1. Initialization: Calculate the length of the array n. Iterate over the array, checking for potential patterns starting at each index i.
2. Pattern formation: For each index i, define a sub-array of length m as the pattern.
3. Pattern checking: Use a nested loop to check for consecutive patterns:
   • Start another loop from the current index i, stepping by m to check the next segment of length m.
   • Compare this segment to the initial pattern.
   • Count consecutive matches. If the count reaches k, return True.
4. Early termination: If the matches do not reach k and the consecutive checking breaks, continue to the next starting index until all possibilities are exhausted.
5. Return False: If no pattern of length m is found k or more times consecutively, return False.

Time Complexity

• Best Case: (O(n)) when a pattern is found early.
• Worst Case: (O((n - m * k + 1) * m)) where n is the length of the array. In the worst case, every possible start index could be checked, each time comparing up to m elements k times. Thus, the complexity is approximately (O(n \cdot m)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?