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

1
2
3
4

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

1
2
3
4

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 <= 100
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

Solution

Method 1 – Sliding Window Pattern Matching

Intuition

The key idea is to check every subarray of length m+1 in nums and compare the difference pattern with the given pattern. If all differences match the pattern, we count it. This works because the constraints are small, so a brute-force sliding window is efficient.

Approach

  1. Loop through all possible starting indices i for subarrays of length m+1 in nums.
  2. For each subarray, compare the difference between consecutive elements with the corresponding value in pattern:
    • If pattern[k] == 1, check nums[i+k+1] > nums[i+k].
    • If pattern[k] == 0, check nums[i+k+1] == nums[i+k].
    • If pattern[k] == -1, check nums[i+k+1] < nums[i+k].
  3. If all checks pass for a subarray, increment the answer.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
        int n = nums.size(), m = pattern.size(), ans = 0;
        for (int i = 0; i + m < n; ++i) {
            bool ok = true;
            for (int k = 0; k < m; ++k) {
                if ((pattern[k] == 1 && nums[i+k+1] <= nums[i+k]) ||
                    (pattern[k] == 0 && nums[i+k+1] != nums[i+k]) ||
                    (pattern[k] == -1 && nums[i+k+1] >= nums[i+k])) {
                    ok = false;
                    break;
                }
            }
            if (ok) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func countMatchingSubarrays(nums []int, pattern []int) int {
    n, m, ans := len(nums), len(pattern), 0
    for i := 0; i+m < n; i++ {
        ok := true
        for k := 0; k < m; k++ {
            if (pattern[k] == 1 && nums[i+k+1] <= nums[i+k]) ||
                (pattern[k] == 0 && nums[i+k+1] != nums[i+k]) ||
                (pattern[k] == -1 && nums[i+k+1] >= nums[i+k]) {
                ok = false
                break
            }
        }
        if ok {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length, m = pattern.length, ans = 0;
        for (int i = 0; i + m < n; ++i) {
            boolean ok = true;
            for (int k = 0; k < m; ++k) {
                if ((pattern[k] == 1 && nums[i+k+1] <= nums[i+k]) ||
                    (pattern[k] == 0 && nums[i+k+1] != nums[i+k]) ||
                    (pattern[k] == -1 && nums[i+k+1] >= nums[i+k])) {
                    ok = false;
                    break;
                }
            }
            if (ok) ++ans;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun countMatchingSubarrays(nums: IntArray, pattern: IntArray): Int {
        val n = nums.size
        val m = pattern.size
        var ans = 0
        for (i in 0..(n - m - 1)) {
            var ok = true
            for (k in 0 until m) {
                if ((pattern[k] == 1 && nums[i+k+1] <= nums[i+k]) ||
                    (pattern[k] == 0 && nums[i+k+1] != nums[i+k]) ||
                    (pattern[k] == -1 && nums[i+k+1] >= nums[i+k])) {
                    ok = false
                    break
                }
            }
            if (ok) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countMatchingSubarrays(self, nums: list[int], pattern: list[int]) -> int:
        n, m, ans = len(nums), len(pattern), 0
        for i in range(n - m):
            ok = True
            for k in range(m):
                if (pattern[k] == 1 and nums[i+k+1] <= nums[i+k]) or \
                   (pattern[k] == 0 and nums[i+k+1] != nums[i+k]) or \
                   (pattern[k] == -1 and nums[i+k+1] >= nums[i+k]):
                    ok = False
                    break
            if ok:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 {
        let n = nums.len();
        let m = pattern.len();
        let mut ans = 0;
        for i in 0..(n - m) {
            let mut ok = true;
            for k in 0..m {
                if (pattern[k] == 1 && nums[i+k+1] <= nums[i+k]) ||
                   (pattern[k] == 0 && nums[i+k+1] != nums[i+k]) ||
                   (pattern[k] == -1 && nums[i+k+1] >= nums[i+k]) {
                    ok = false;
                    break;
                }
            }
            if ok {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    countMatchingSubarrays(nums: number[], pattern: number[]): number {
        const n = nums.length, m = pattern.length;
        let ans = 0;
        for (let i = 0; i + m < n; ++i) {
            let ok = true;
            for (let k = 0; k < m; ++k) {
                if ((pattern[k] === 1 && nums[i+k+1] <= nums[i+k]) ||
                    (pattern[k] === 0 && nums[i+k+1] !== nums[i+k]) ||
                    (pattern[k] === -1 && nums[i+k+1] >= nums[i+k])) {
                    ok = false;
                    break;
                }
            }
            if (ok) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n is the length of nums and m is the length of pattern. For each of the n-m subarrays, we check m conditions.
  • 🧺 Space complexity: O(1), as we use only a constant amount of extra space for counters and flags.