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 I

Difficulty: Medium

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 the following conditions hold for each element pattern[k]:

  • nums[i + k + 1] > nums[i + k] if pattern[k] == 1.
  • nums[i + k + 1] == nums[i + k] if pattern[k] == 0.
  • nums[i + k + 1] < nums[i + k] if pattern[k] == -1.

Return the count of subarrays in nums that match the pattern.

Key Insights

  • The problem requires checking subarrays against a specific pattern of relationships (increasing, equal, decreasing).
  • The length of the subarray to check is m + 1, where m is the length of the pattern.
  • Efficiently checking each subarray requires understanding how to translate the pattern into comparisons between elements of nums.

Space and Time Complexity

Time Complexity: O(n * m) - We check each subarray of size m + 1 for every starting index. Space Complexity: O(1) - We use a fixed amount of extra space regardless of input size.

Solution

To solve this problem, we iterate over each starting index of the subarray in the nums array. For each starting index, we check if the subarray of length m + 1 matches the given pattern. We utilize a nested loop where the outer loop iterates through the starting indices of the potential subarrays, and the inner loop checks the conditions defined in the pattern. Specifically, we compare adjacent elements based on the values in the pattern array (-1 for less than, 0 for equal, and 1 for greater than). If all conditions are satisfied for a particular subarray, we increment our count.

Code Solutions

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

    # Loop through each possible starting index for the subarray
    for i in range(n - m):
        match = True
        
        # Check if the subarray matches the pattern
        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