LeetCode 795: Number of Subarrays with Bounded Maximum

A clear explanation of counting contiguous subarrays whose maximum value lies inside a given inclusive range.

leetcodearraytwo-pointerssliding-window

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

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:

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:

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:

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

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

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:

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:

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:

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