Number of Subarrays That Match a Pattern II

Problem

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 thecount of subarrays in nums that match the pattern.

Examples

Example 1

Input: nums = [1,2,3,4,5,6], pattern = [1,1]
Output: 4
Explanation: The pattern [1,1] indicates that we are looking for strictly increasing subarrays of size 3. In the array nums, the subarrays [1,2,3], [2,3,4], [3,4,5], and [4,5,6] match this pattern.
Hence, there are 4 subarrays in nums that match the pattern.

Example 2

Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output: 2
Explanation: Here, the pattern [1,0,-1] indicates that we are looking for a sequence where the first number is smaller than the second, the second is equal to the third, and the third is greater than the fourth. In the array nums, the subarrays [1,4,4,1], and [3,5,5,3] match this pattern.
Hence, there are 2 subarrays in nums that match the pattern.

Constraints

• 2 <= n == nums.length <= 10^6
• 1 <= nums[i] <= 10^9
• 1 <= m == pattern.length < n
• -1 <= pattern[i] <= 1

Solution

Method 1 – Sliding Window with Pattern Matching

Intuition

We need to count the number of subarrays of length m+1 in nums that match a given pattern of differences. For each window of size m+1, we can check if the sequence of differences between consecutive elements matches the pattern. Since the constraints are large, we can precompute the difference array and use a rolling hash or direct comparison for efficiency.

Approach

1. Compute the difference array diffs where diffs[i] = sign(nums[i+1] - nums[i]) for all i.
2. For each window of length m in diffs, compare it to the pattern. If it matches, increment the count.
3. The answer is the total number of such windows.

Code

Python

from typing import List

def countMatchingSubarrays(nums: List[int], pattern: List[int]) -> int:
    n, m = len(nums), len(pattern)
    def sign(x):
        return 1 if x > 0 else -1 if x < 0 else 0
    diffs = [sign(nums[i+1] - nums[i]) for i in range(n-1)]
    count = 0
    for i in range(n - m - 0):
        if diffs[i:i+m] == pattern:
            count += 1
    return count

C++

#include <vector>
using namespace std;

int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
    int n = nums.size(), m = pattern.size(), res = 0;
    auto sign = [](int x) { return x > 0 ? 1 : (x < 0 ? -1 : 0); };
    vector<int> diffs(n-1);
    for (int i = 0; i < n-1; ++i) diffs[i] = sign(nums[i+1] - nums[i]);
    for (int i = 0; i + m < n; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (diffs[i+j] != pattern[j]) { match = false; break; }
        }
        if (match) ++res;
    }
    return res;
}

Java

public class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length, m = pattern.length, res = 0;
        int[] diffs = new int[n-1];
        for (int i = 0; i < n-1; ++i) {
            int d = nums[i+1] - nums[i];
            diffs[i] = d > 0 ? 1 : (d < 0 ? -1 : 0);
        }
        for (int i = 0; i + m < n; ++i) {
            boolean match = true;
            for (int j = 0; j < m; ++j) {
                if (diffs[i+j] != pattern[j]) { match = false; break; }
            }
            if (match) ++res;
        }
        return res;
    }
}

Kotlin

fun countMatchingSubarrays(nums: IntArray, pattern: IntArray): Int {
    val n = nums.size
    val m = pattern.size
    val diffs = IntArray(n-1) { i ->
        when {
            nums[i+1] > nums[i] -> 1
            nums[i+1] < nums[i] -> -1
            else -> 0
        }
    }
    var res = 0
    for (i in 0..n-m-1) {
        if ((0 until m).all { diffs[i+it] == pattern[it] }) res++
    }
    return res
}

Go

func countMatchingSubarrays(nums []int, pattern []int) int {
    n, m := len(nums), len(pattern)
    diffs := make([]int, n-1)
    for i := 0; i < n-1; i++ {
        if nums[i+1] > nums[i] {
            diffs[i] = 1
        } else if nums[i+1] < nums[i] {
            diffs[i] = -1
        } else {
            diffs[i] = 0
        }
    }
    res := 0
    for i := 0; i+m < n; i++ {
        match := true
        for j := 0; j < m; j++ {
            if diffs[i+j] != pattern[j] {
                match = false
                break
            }
        }
        if match {
            res++
        }
    }
    return res
}

Rust

pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = pattern.len();
    let mut diffs = vec![0; n-1];
    for i in 0..n-1 {
        diffs[i] = if nums[i+1] > nums[i] { 1 } else if nums[i+1] < nums[i] { -1 } else { 0 };
    }
    let mut res = 0;
    for i in 0..=n-m-1 {
        if (0..m).all(|j| diffs[i+j] == pattern[j]) {
            res += 1;
        }
    }
    res
}

TypeScript

function countMatchingSubarrays(nums: number[], pattern: number[]): number {
    const n = nums.length, m = pattern.length;
    const diffs = Array(n-1).fill(0).map((_, i) =>
        nums[i+1] > nums[i] ? 1 : nums[i+1] < nums[i] ? -1 : 0
    );
    let res = 0;
    for (let i = 0; i + m < n; ++i) {
        let match = true;
        for (let j = 0; j < m; ++j) {
            if (diffs[i+j] !== pattern[j]) { match = false; break; }
        }
        if (match) res++;
    }
    return res;
}

Complexity

• ⏰ Time complexity: O(n * m)
• 🧺 Space complexity: O(n)