Sawtooth Subarray Count - Array Coding Interview

Question

## Problem

An array is "sawtooth" if its elements alternate strictly: each element is either strictly greater than both neighbors or strictly less than both neighbors (i.e., it alternates up-down or down-up). A single element or two elements always qualify.

Count the number of sawtooth subarrays of length >= 2.

```python
def count_sawtooth_subarrays(nums: list[int]) -> int:
    ...
```

**Example:**
```
Input:  [1, 3, 2, 4, 3]
Output: 9
Subarrays: [1,3],[3,2],[2,4],[4,3],[1,3,2],[3,2,4],[2,4,3],[1,3,2,4],[3,2,4,3] -- verify each.
```

## Approach

Compute a "direction" array where `d[i] = 1` if `nums[i] > nums[i-1]`, `-1` if less, `0` if equal. A subarray ending at `i` extends the sawtooth as long as `d[i] != d[i-1]` and `d[i] != 0`. Maintain current run length.

For each position, the number of new valid sawtooth subarrays ending there = current run length.

## Follow-ups
- What is the time and space complexity of the direction-array approach?
- How does your solution handle equal consecutive elements?
- Extend to count sawtooth subarrays of exactly length `k`.

Sawtooth Subarray Count - Array Coding Interview

Question Details

Full Details

Topics

More from Codesignal