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:

left <= max(subarray) <= right

The subarray must be contiguous.

Input and Output

Function shape:

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

Examples

Example 1:

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

The valid subarrays are:

[2]
[2, 1]
[3]

Their maximum values are 2, 2, and 3.

So the answer is:

3

Example 2:

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:

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:

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

we can count:

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

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

Define:

count_at_most(bound)

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

Then the answer is:

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:

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

Scan:

Total subarrays with maximum <= 3:

4

They are:

[2], [2, 1], [1], [3]

Now count maximum <= 1:

[1]

So the final answer is:

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:

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:

count_at_most(right) - count_at_most(left - 1)

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

Complexity

Implementation

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:

def count_at_most(bound: int) -> int:

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

length = 0

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

if num <= bound:
    length += 1

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

else:
    length = 0

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

total += length

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

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

Alternative One-Pass Version

We can also solve it in one scan.

Track:

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

last_valid - last_too_large

Implementation:

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

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: