Count Subarrays Whose Step-by-Step Changes Match an Up, Flat, Down Pattern
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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
```python
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**
```text
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**
```text
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**
```text
Input: nums = [4, 3, 2, 1], pattern = [1]
Output: 0
```
Every neighboring pair decreases, so no subarray of length 2 rises.
Overview: Count the fixed-length windows of an integer array whose consecutive rises, equal steps, and drops follow a given pattern of 1, 0, and -1 values, counting overlapping matches separately. Tests turning a comparison rule into an exact window check with correct index bounds.
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 `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.
- 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.
### Example 1
```text
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
```text
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.
### Constraints
- `2 <= n <= 100`
- `1 <= m < n`
- `1 <= nums[i] <= 10^9`
- Every `pattern[k]` is one of `-1`, `0` or `1`.
No value exceeds 2^31 - 1: every element fits in a signed 32-bit integer, and the answer is an integer from `0` to `n - m`.
Constraints
- 2 <= n <= 100, where n is the length of nums
- 1 <= m < n, where m is the length of pattern
- 1 <= nums[i] <= 10^9
- Every pattern[k] is one of -1, 0 or 1
Examples
Input: ([1, 3, 2, 4, 3, 3], [1, -1])
Expected Output: 2
Explanation: Source example 1: the windows starting at 0 and 2 go up then down.
Input: ([5, 5, 5, 5], [0, 0])
Expected Output: 2
Explanation: Source example 2: the two overlapping all-equal windows each count.
Hints
- Each pattern entry depends only on one pair of neighbors, nums[i + k] and nums[i + k + 1], compared strictly or for equality.
- A window needs m + 1 elements, so be careful about which starting indices are valid: the last one is n - m - 1.
- Windows may share elements; check each start independently and count each matching start once.