Count Subarrays Whose Step-by-Step Changes Match an Up, Flat, Down Pattern

You are given an integer array nums of length n and an array pattern of length m whose values are each -1, 0 or 1. Each pattern value describes the relationship between two neighboring numbers:

• 1: the next number is strictly greater than the current one;
• 0: the next number is equal to the current one;
• -1: the next number is strictly smaller than the current one.

The contiguous subarray of nums that starts at index i and has exactly m + 1 elements matches the pattern if, for every k from 0 to m - 1, the relationship between nums[i + k] and nums[i + k + 1] is the one described by pattern[k]. Return the number of starting indices i whose subarray matches.

Function Signature

def count_matching_subarrays(nums: list[int], pattern: list[int]) -> int:

Rules

• Only subarrays of exactly m + 1 elements are considered, one for each starting index i with 0 <= i <= n - m - 1.
• Matching subarrays may overlap; each matching starting index counts once.
• Return 0 if no subarray matches.

Constraints

• 2 <= n <= 100
• 1 <= m < n
• 1 <= nums[i] <= 10^9
• Every pattern[k] is one of -1, 0 or 1.

Examples

Example 1

Input:  nums = [1, 3, 2, 4, 3, 3], pattern = [1, -1]
Output: 2

The subarrays of length 3 are [1, 3, 2] (up, then down: matches), [3, 2, 4] (down, then up), [2, 4, 3] (up, then down: matches) and [4, 3, 3] (down, then equal).

Example 2

Input:  nums = [5, 5, 5, 5], pattern = [0, 0]
Output: 2

The subarrays starting at indices 0 and 1 are both [5, 5, 5]. They overlap, and each counts.

Example 3

Input:  nums = [4, 3, 2, 1], pattern = [1]
Output: 0

Every neighboring pair decreases, so no subarray of length 2 rises.

Count Subarrays Matching a Rise-Equal-Fall Pattern

Hints

1. Each pattern entry depends only on one pair of neighbors, nums[i + k] and nums[i + k + 1], compared strictly or for equality.
2. A window needs m + 1 elements, so be careful about which starting indices are valid: the last one is n - m - 1.
3. Windows may share elements; check each start independently and count each matching start once.

Approach

Examine every starting index i from 0 through n - m - 1; these are exactly the starts whose window of m + 1 elements fits inside nums. For a given start, walk k from 0 to m - 1 and classify the neighboring pair (nums[i + k], nums[i + k + 1]) as 1 when the second value is strictly larger, 0 when the two are equal, and -1 when the second is strictly smaller. Stop at the first k whose classification differs from pattern[k]; if no mismatch occurs, the window matches and the count increases by one. Invariant: after start i has been processed, count equals the number of matching starts among 0..i. Correctness: a window matches precisely when all m of its neighbor relationships agree with the pattern, which is exactly what the inner loop checks, and every start is examined once, so overlapping matches are each counted once and nothing is double-counted. Edge cases: when m = n - 1 there is exactly one window covering the whole array; because the comparisons are strict, an equal pair matches only 0 and never 1 or -1; when no window matches the answer is 0. Values are at most 10^9 and are only compared, never added, so 32-bit integers suffice, and the answer is at most n - m.

• Time complexity: O((n - m) * m)
• Space complexity: O(1)