We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays That Match a Pattern II

Number: 3290

Difficulty: Hard

Paid? No

Companies: Autodesk

Problem Description

Given an integer array nums and a pattern array (whose elements can be -1, 0, or 1), we want to count how many subarrays of length m+1 (where m is the length of the pattern) satisfy the following conditions for every index k (0 ≤ k < m):

  • If pattern[k] == 1, then nums[i + k + 1] > nums[i + k].
  • If pattern[k] == 0, then nums[i + k + 1] == nums[i + k].
  • If pattern[k] == -1, then nums[i + k + 1] < nums[i + k].

Key Insights

  • Transform the nums array into a differences array (of length n-1) where each element represents the relation (+1, 0, or -1) between consecutive elements.
  • The problem reduces to pattern matching: count occurrences of the given pattern in the differences array.
  • A linear time pattern matching algorithm such as the Knuth-Morris-Pratt (KMP) method is well-suited due to the large input size.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of nums and m is the length of pattern.
Space Complexity: O(n), due to the differences array.

Solution

We first preprocess the nums array to build a differences array where each element is determined by comparing consecutive numbers. Then, we use the KMP algorithm to find the number of occurrences of the pattern in this differences array.
Key steps include:

  1. Build the differences array using the given relation.
  2. Compute the partial match (failure) table for the pattern.
  3. Use the KMP matching method to scan through the differences array and count matches. This approach guarantees that each element is processed only a constant number of times while maintaining the overall linear time complexity.

Code Solutions

def count_matching_subarrays(nums, pattern):
    # Build the differences (relations) array from nums.
    n = len(nums)
    diffs = []
    for i in range(n - 1):
        if nums[i + 1] > nums[i]:
            diffs.append(1)
        elif nums[i + 1] < nums[i]:
            diffs.append(-1)
        else:
            diffs.append(0)

    # KMP preprocessing: Compute the longest prefix that is also a suffix (lps) array.
    m = len(pattern)
    lps = [0] * m
    length = 0  # length of the previous longest prefix suffix
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    # KMP search on the diffs array.
    count = 0
    i = 0  # index for diffs
    j = 0  # index for pattern
    diff_len = len(diffs)
    while i < diff_len:
        if pattern[j] == diffs[i]:
            i += 1
            j += 1
            if j == m:
                count += 1               # found a match
                j = lps[j - 1]  # continue search for overlapping patterns
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return count

# Example usage:
nums = [1, 4, 4, 1, 3, 5, 5, 3]
pattern = [1, 0, -1]
print(count_matching_subarrays(nums, pattern))  # Output: 2
← Back to All Questions