Count Windows That Follow an Increase, Equal, Decrease Pattern
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given an integer array `numbers` and an array `pattern` whose values are each `1`, `0` or `-1`. Let `m = len(pattern)`. A window of `m + 1` consecutive elements, `numbers[s]` through `numbers[s + m]`, follows the pattern when every step inside it has the direction that `pattern` gives for that step:
- `pattern[k] == 1` means `numbers[s + k + 1] > numbers[s + k]`
- `pattern[k] == 0` means `numbers[s + k + 1] == numbers[s + k]`
- `pattern[k] == -1` means `numbers[s + k + 1] < numbers[s + k]`
Return the number of starting indices `s` whose window follows the pattern.
### Function Signature
```python
def count_pattern_windows(numbers: list[int], pattern: list[int]) -> int:
```
### Rules
- A window must lie entirely inside `numbers`, so `s` ranges from `0` to `len(numbers) - m - 1`.
- Every one of the `m` conditions must hold; a single mismatched step disqualifies the window.
- Windows may overlap, and each matching starting index is counted once.
- Return `0` when no window matches.
### Constraints
- `2 <= len(numbers) <= 10^5`
- `1 <= len(pattern) < len(numbers)`
- `-10^9 <= numbers[i] <= 10^9`
- every `pattern[k]` is `1`, `0` or `-1`
### Examples
**Example 1**
```text
Input: numbers = [3, 7, 5, 5, 8, 7], pattern = [-1, 0, 1]
Output: 1
```
The only matching window starts at index 1: `[7, 5, 5, 8]` steps down from 7 to 5, stays equal from 5 to 5, then steps up from 5 to 8. Put differently, the elements `5, 5, 8` at indices 2 to 4 each compare with the element just before them as the pattern requires. The windows starting at index 0 (`[3, 7, 5, 5]`, whose first step goes up) and index 2 (`[5, 5, 8, 7]`, whose first step is equal) do not match.
**Example 2**
```text
Input: numbers = [2, 2, 2, 2], pattern = [0, 0]
Output: 2
```
The windows starting at indices 0 and 1 both stay equal twice; overlapping windows are counted separately.
**Example 3**
```text
Input: numbers = [5, 4, 5, 4, 5], pattern = [1, -1]
Output: 1
```
Only the window starting at index 1, `[4, 5, 4]`, goes up and then down. The windows starting at indices 0 and 2 begin with a decrease.
Overview: A coding question that gives an integer array and a pattern of 1, 0 and -1 values standing for an increase, an equal step and a decrease, and asks how many windows of consecutive elements follow the pattern exactly. It tests translating pairwise comparisons into steps and counting overlapping matches efficiently.
Read the full Capital One Software Engineer interview experience this question came from
You are given an integer array `numbers` and an array `pattern` whose entries are each `1`, `0` or `-1`. Let `m = len(pattern)`. A **window** is a run of `m + 1` consecutive elements, `numbers[s]` through `numbers[s + m]`. The window **follows the pattern** when each of its `m` steps has the direction that `pattern` gives for that step:
- `pattern[k] == 1` means `numbers[s + k + 1] > numbers[s + k]` (the step goes up)
- `pattern[k] == 0` means `numbers[s + k + 1] == numbers[s + k]` (the step stays equal)
- `pattern[k] == -1` means `numbers[s + k + 1] < numbers[s + k]` (the step goes down)
Return the number of starting indices `s` whose window follows the pattern.
### Rules
- A window must lie entirely inside `numbers`, so `s` ranges from `0` to `len(numbers) - m - 1`.
- Every one of the `m` conditions must hold; a single mismatched step disqualifies the window.
- Windows may overlap, and each matching starting index is counted once.
- Return `0` when no window matches.
### Example 1
```text
Input: numbers = [3, 7, 5, 5, 8, 7], pattern = [-1, 0, 1]
Output: 1
```
Only the window starting at index 1, `[7, 5, 5, 8]`, matches: it steps down from 7 to 5, stays equal from 5 to 5, then steps up from 5 to 8. The window starting at index 0 (`[3, 7, 5, 5]`) begins by going up, and the window starting at index 2 (`[5, 5, 8, 7]`) begins with an equal step.
### Example 2
```text
Input: numbers = [2, 2, 2, 2], pattern = [0, 0]
Output: 2
```
The windows starting at indices 0 and 1 both stay equal twice; overlapping windows are counted separately.
### Constraints
- `2 <= len(numbers) <= 10^5`
- `1 <= len(pattern) < len(numbers)`
- `-10^9 <= numbers[i] <= 10^9`
- every `pattern[k]` is `1`, `0` or `-1`
No value exceeds 2^31 - 1: every element fits a signed 32-bit integer and the returned count is at most `len(numbers) - len(pattern)`, so a 32-bit `int` is sufficient in every language.
Constraints
- 2 <= len(numbers) <= 10^5
- 1 <= len(pattern) < len(numbers)
- -10^9 <= numbers[i] <= 10^9
- every pattern[k] is 1, 0 or -1
Examples
Input: ([3, 7, 5, 5, 8, 7], [-1, 0, 1])
Expected Output: 1
Explanation: Source example 1: only the window at index 1, [7, 5, 5, 8], goes down, stays equal, then goes up.
Input: ([2, 2, 2, 2], [0, 0])
Expected Output: 2
Explanation: Source example 2: overlapping equal windows at indices 0 and 1 are both counted.
Hints
- Every condition looks at just two neighbouring elements. Try describing each adjacent pair of numbers by a single value before you think about whole windows.
- After that rewrite, ask what a matching window looks like in the rewritten sequence and how the range of valid starting indices maps onto it.
- The pattern can be almost as long as numbers, so re-checking every window from its first step can take quadratic time. Look for a way to reuse what earlier comparisons already told you when windows overlap.