# LeetCode 795: Number of Subarrays with Bounded Maximum

## Problem Restatement

We are given an integer array `nums` and two integers `left` and `right`.

We need to count how many non-empty contiguous subarrays have a maximum value in this range:

```python
left <= max(subarray) <= right
```

The subarray must be contiguous.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums`, `left`, and `right` |
| Output | Number of valid non-empty contiguous subarrays |
| Valid subarray | Its maximum value is between `left` and `right` |
| Range | Inclusive: `[left, right]` |

Function shape:

```python
class Solution:
    def numSubarrayBoundedMax(
        self,
        nums: list[int],
        left: int,
        right: int
    ) -> int:
        ...
```

## Examples

Example 1:

```python
nums = [2, 1, 4, 3]
left = 2
right = 3
```

The valid subarrays are:

```text
[2]
[2, 1]
[3]
```

Their maximum values are `2`, `2`, and `3`.

So the answer is:

```python
3
```

Example 2:

```python
nums = [2, 9, 2, 5, 6]
left = 2
right = 8
```

The value `9` is greater than `right`, so any subarray containing `9` is invalid.

The valid subarrays are inside the segments around `9`.

The answer is:

```python
7
```

## First Thought: Check Every Subarray

A direct solution is to generate every subarray.

For each start index, extend the end index one step at a time while tracking the maximum value.

Then count the subarray if its maximum is between `left` and `right`.

This works, but there are `O(n^2)` subarrays.

For large input, this is too slow.

## Key Insight

Instead of asking:

```text
How many subarrays have maximum in [left, right]?
```

we can count:

```text
subarrays with maximum <= right
-
subarrays with maximum < left
```

That gives exactly the subarrays whose maximum is at least `left` and at most `right`.

Define:

```python
count_at_most(bound)
```

as the number of subarrays whose maximum value is at most `bound`.

Then the answer is:

```python
count_at_most(right) - count_at_most(left - 1)
```

## Counting Subarrays With Maximum At Most a Bound

Scan the array from left to right.

Keep `length`, the number of consecutive elements ending at the current index that are `<= bound`.

If `nums[i] <= bound`, then every subarray ending at `i` and starting inside this valid streak is valid.

So we add `length` to the answer.

If `nums[i] > bound`, the streak breaks, and `length` becomes `0`.

Example:

```python
nums = [2, 1, 4, 3]
bound = 3
```

Scan:

| Index | Value | Current valid streak | Added |
|---:|---:|---:|---:|
| `0` | `2` | `1` | `1` |
| `1` | `1` | `2` | `2` |
| `2` | `4` | `0` | `0` |
| `3` | `3` | `1` | `1` |

Total subarrays with maximum `<= 3`:

```python
4
```

They are:

```text
[2], [2, 1], [1], [3]
```

Now count maximum `<= 1`:

```text
[1]
```

So the final answer is:

```python
4 - 1 = 3
```

## Algorithm

1. Define `count_at_most(bound)`.
2. Inside it:
   1. Set `total = 0`.
   2. Set `length = 0`.
   3. For each number:
      1. If `num <= bound`, increment `length`.
      2. Otherwise, reset `length = 0`.
      3. Add `length` to `total`.
3. Return:

```python
count_at_most(right) - count_at_most(left - 1)
```

## Correctness

For a fixed `bound`, `count_at_most(bound)` counts exactly the subarrays whose maximum is at most `bound`.

When `nums[i] <= bound`, the current valid streak length tells us how many contiguous subarrays ending at `i` contain only values `<= bound`. Each of those subarrays has maximum at most `bound`, so adding `length` is correct.

When `nums[i] > bound`, no valid subarray ending at `i` can include this value. The valid streak must reset to `0`.

Therefore, `count_at_most(bound)` returns the number of subarrays with maximum value at most `bound`.

A subarray has maximum in `[left, right]` exactly when its maximum is at most `right` and not at most `left - 1`. So subtracting:

```python
count_at_most(right) - count_at_most(left - 1)
```

counts exactly the subarrays whose maximum lies in the required inclusive range.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array twice |
| Space | `O(1)` | Only counters are stored |

## Implementation

```python
class Solution:
    def numSubarrayBoundedMax(
        self,
        nums: list[int],
        left: int,
        right: int
    ) -> int:
        def count_at_most(bound: int) -> int:
            total = 0
            length = 0

            for num in nums:
                if num <= bound:
                    length += 1
                else:
                    length = 0

                total += length

            return total

        return count_at_most(right) - count_at_most(left - 1)
```

## Code Explanation

The helper function counts subarrays whose maximum is at most `bound`:

```python
def count_at_most(bound: int) -> int:
```

`length` stores the current streak of values that are `<= bound`:

```python
length = 0
```

If the current number is allowed, we extend the streak:

```python
if num <= bound:
    length += 1
```

If the current number is too large, every subarray ending here is invalid, so we reset:

```python
else:
    length = 0
```

Each valid streak ending at the current index contributes `length` subarrays:

```python
total += length
```

Finally, subtract the count of subarrays whose maximum is too small:

```python
return count_at_most(right) - count_at_most(left - 1)
```

## Alternative One-Pass Version

We can also solve it in one scan.

Track:

| Variable | Meaning |
|---|---|
| `last_too_large` | Last index where `nums[i] > right` |
| `last_valid` | Last index where `nums[i] >= left` |

At index `i`, the number of valid subarrays ending at `i` is:

```python
last_valid - last_too_large
```

Implementation:

```python
class Solution:
    def numSubarrayBoundedMax(
        self,
        nums: list[int],
        left: int,
        right: int
    ) -> int:
        answer = 0
        last_too_large = -1
        last_valid = -1

        for i, num in enumerate(nums):
            if num > right:
                last_too_large = i

            if num >= left:
                last_valid = i

            answer += last_valid - last_too_large

        return answer
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numSubarrayBoundedMax([2, 1, 4, 3], 2, 3) == 3
    assert s.numSubarrayBoundedMax([2, 9, 2, 5, 6], 2, 8) == 7

    assert s.numSubarrayBoundedMax([1, 1, 1], 2, 3) == 0
    assert s.numSubarrayBoundedMax([2, 2, 2], 2, 2) == 6
    assert s.numSubarrayBoundedMax([4, 4, 4], 2, 3) == 0

    assert s.numSubarrayBoundedMax([1, 2, 3, 4], 2, 3) == 5

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `[2, 1, 4, 3]` | Standard example |
| `[2, 9, 2, 5, 6]` | Contains a value greater than `right` |
| All values too small | No subarray reaches `left` |
| All values exactly valid | Every subarray is valid |
| All values too large | Every subarray is invalid |
| Mixed increasing values | Checks range boundaries |