algoadvance

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

Problem Statement

Given an array of positive integers arr, find a pattern of length m that is repeated at least k times. A pattern is a subarray (contiguous subarray) of arr that:

• occurs at least k times.
• the distance between each occurrence of the pattern is exactly m.

Return true if there exists such a pattern and false otherwise.

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 times.

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 times.

Example 3:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) of length 2 is repeated 2 times but not 3 times.

Clarifying Questions

1. Can the array have negative or zero values?
   • No, the array contains only positive integers.
2. Should the pattern be contiguous in its repetitions, or can there be gaps as long as the distance between repetitions is m?
   • The pattern must be contiguous and every repetition should be exactly m distance from each other.
3. Can m or k be zero or negative?
   • No, m and k are positive integers.

Strategy

1. Sliding Window Approach: We will utilize a sliding window method to check for patterns:
   • Iterate through the array up to the length minus m times k to avoid out-of-bound errors.
   • Use nested loops to check for patterns of length m starting from each index.
   • For each subarray of length m, check if it repeats k times consecutively.
2. Pattern Matching:
   • For a given starting index, extract a subarray of length m.
   • Check if this subarray is repeated exactly k times by comparing the subsequent elements in blocks of size m.

Code

public class DetectPattern {
    public boolean containsPattern(int[] arr, int m, int k) {
        int n = arr.length;
        
        // Iterate through the array up to length minus (m * (k - 1))
        for (int i = 0; i <= n - m * k; i++) {
            boolean matchFound = true;
            // Check the pattern in chunks of size m
            for (int j = 0; j < m * (k - 1); j++) {
                if (arr[i + j] != arr[i + j + m]) {
                    matchFound = false;
                    break;
                }
            }
            if (matchFound) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        DetectPattern dp = new DetectPattern();
        
        // Test cases
        System.out.println(dp.containsPattern(new int[]{1,2,4,4,4,4}, 1, 3)); // true
        System.out.println(dp.containsPattern(new int[]{1,2,1,2,1,1,1,3}, 2, 2)); // true
        System.out.println(dp.containsPattern(new int[]{1,2,1,2,1,1,1,3}, 2, 3)); // false
    }
}

Time Complexity

• Time Complexity: O(n * m * k)
  • We iterate through the array up to n - m * k, checking for patterns. Each pattern check involves comparing up to m * (k - 1) elements.
• Space Complexity: O(1)
  • We only use a constant amount of extra space for variables.

By adapting this approach, we ensure an efficient and clear solution to the problem.

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

• 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?