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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays That Match a Pattern II

Difficulty: Hard

Problem Description

You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m consisting of integers -1, 0, and 1. A subarray nums[i..j] of size m + 1 is said to match the pattern if specific conditions hold for each element pattern[k]. The task is to return the count of subarrays in nums that match the pattern.

Key Insights

  • The subarrays need to be of size m + 1.
  • The matching conditions depend on the values in pattern:
    • pattern[k] == 1 requires a strictly increasing sequence.
    • pattern[k] == 0 requires adjacent elements to be equal.
    • pattern[k] == -1 requires a strictly decreasing sequence.
  • A sliding window or two-pointer technique can be utilized to efficiently count the matching subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves iterating through the nums array while maintaining a window of size m + 1. For each starting index, we check if the subarray matches the pattern using a loop that examines each condition specified in pattern. If a match is found, we increase our count. This approach ensures that we only make a single pass through the nums array, achieving linear time complexity.

Code Solutions

def count_subarrays(nums, pattern):
    n = len(nums)
    m = len(pattern)
    count = 0

    for i in range(n - m):
        match = True
        for k in range(m):
            if pattern[k] == 1 and not (nums[i + k + 1] > nums[i + k]):
                match = False
                break
            elif pattern[k] == 0 and not (nums[i + k + 1] == nums[i + k]):
                match = False
                break
            elif pattern[k] == -1 and not (nums[i + k + 1] < nums[i + k]):
                match = False
                break

        if match:
            count += 1

    return count
← Back to All Questions