LeetCode Solutions Blog

Number of Subarrays That Match a Pattern I

Number: 3269

Difficulty: Medium

Paid? No

Companies: Autodesk

Problem Description

Given an integer array nums and a pattern array consisting of -1, 0, and 1, count the number of subarrays in nums of size (pattern.length+1) that match the pattern condition. For each element pattern[k] in the pattern, the corresponding adjacent elements in the subarray must satisfy:

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

Key Insights

Since the subarray length is fixed at (pattern.length + 1), use a sliding window to check each candidate subarray.
For each subarray, iterate through its adjacent pairs and verify if they satisfy the corresponding pattern condition.
Given the constraints (n up to 100), a straightforward O(n*m) solution is efficient.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of nums and m is the length of the pattern. Space Complexity: O(1) additional space.

Solution

We slide a window of length (pattern.length + 1) over the array nums. For each window:

Iterate through the window and compare consecutive elements based on the pattern.
If all comparisons meet the specified condition, count the subarray as a valid match.
Return the total count after processing all possible subarrays.

Code Solutions

# Python solution with line-by-line comments

def countMatches(nums, pattern):
    # Determine lengths of nums and the required subarray size (pattern length + 1)
    n = len(nums)
    m = len(pattern)
    count = 0  # To store the number of matching subarrays
    
    # Iterate over each starting index for subarrays of length m + 1
    for i in range(n - m):
        matches = True  # Flag to check if current subarray matches the pattern
        # Check each adjacent pair in the subarray
        for k in range(m):
            # Compare the adjacent numbers based on the pattern value
            if pattern[k] == 1 and not (nums[i + k + 1] > nums[i + k]):
                matches = False
                break
            elif pattern[k] == 0 and not (nums[i + k + 1] == nums[i + k]):
                matches = False
                break
            elif pattern[k] == -1 and not (nums[i + k + 1] < nums[i + k]):
                matches = False
                break
        # If all pairs satisfy the condition, increase count
        if matches:
            count += 1
    return count

# Example usage:
print(countMatches([1,2,3,4,5,6], [1,1]))