LeetCode 795 - Number of Subarrays with Bounded Maximum

LeetCode Problem 795

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to count how many contiguous, non-empty subarrays have a maximum element that lies within the inclusive range [left, right].

A subarray is a continuous segment of the original array. For every possible subarray, we look at its maximum value. If that maximum is at least left and at most right, then the subarray is considered valid and contributes to the final answer.

For example, if:

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

then:

• [2] is valid because its maximum is 2
• [2,1] is valid because its maximum is 2
• [3] is valid because its maximum is 3
• [4] is invalid because its maximum is 4, which exceeds right

The goal is to return the total count of valid subarrays.

The constraints are important:

• nums.length can be as large as 100000
• Each number can be as large as 10^9

These limits immediately tell us that an algorithm with quadratic complexity, such as checking every subarray explicitly, will likely be too slow. Since there are O(n^2) possible subarrays, we need something closer to linear time.

Several edge cases are especially important:

• Arrays where every value is greater than right
• Arrays where every value is smaller than left
• Arrays containing many valid overlapping subarrays
• Single-element arrays
• Large stretches of values less than left, which can extend previously valid subarrays
• Values greater than right, which completely break valid subarray continuity

A correct solution must carefully handle all of these situations efficiently.

Approaches

Brute Force Approach

The most straightforward solution is to generate every possible subarray and compute its maximum value.

For each starting index i, we extend the subarray one element at a time toward the right. While extending, we maintain the current maximum. If the maximum falls inside [left, right], we increment the answer.

This approach is correct because it explicitly checks every possible subarray and directly verifies the problem condition.

However, the number of subarrays in an array of length n is:

n * (n + 1) / 2

which is O(n^2).

With n = 100000, this becomes far too large. Even if maximum values are maintained incrementally, the algorithm still requires quadratic time.

Optimal Approach

The key insight is that we do not need to evaluate every subarray individually.

Instead, we can count how many valid subarrays end at each index.

Consider scanning the array from left to right. At each position:

• If the current value is greater than right, then no subarray ending here can be valid.
• If the current value lies within [left, right], then every subarray starting after the last invalid element becomes valid.
• If the current value is smaller than left, then it cannot independently create a valid subarray, but it can extend previously valid ones.

To make this work efficiently, we track:

• last_invalid, the most recent index where nums[i] > right
• last_valid, the most recent index where left <= nums[i] <= right

At each position:

• The number of valid subarrays ending at the current index equals:

last_valid - last_invalid

if last_valid > last_invalid.

This transforms the problem into a single linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every subarray explicitly
Optimal	O(n)	O(1)	Counts valid subarrays during one pass

Algorithm Walkthrough

Optimal Sliding Window Counting Strategy

1. Initialize three variables:

• last_invalid = -1
• last_valid = -1
• answer = 0

last_invalid stores the latest position where the value exceeded right. Any subarray crossing this index becomes invalid.

last_valid stores the latest position where the value was inside [left, right]. This ensures the subarray contains at least one acceptable maximum. 2. Traverse the array from left to right. 3. For each index i:

• If nums[i] > right, update:

last_invalid = i

because this value makes every subarray containing it invalid. 4. If nums[i] lies inside [left, right], update:

last_valid = i

because this element can serve as the valid maximum for subarrays ending at i. 5. Compute how many valid subarrays end at index i.

Any subarray:

• must start after last_invalid
• must include last_valid

Therefore, the number of valid starting positions is:

last_valid - last_invalid

6. Add this quantity to the answer if it is positive.
7. Continue until the entire array has been processed.
8. Return the final answer.

Why it works

The algorithm maintains an important invariant:

• Every valid subarray ending at index i must begin after the most recent invalid element.
• Every valid subarray must contain at least one element within [left, right].

last_invalid guarantees we never include a value greater than right, while last_valid guarantees the subarray contains a valid maximum candidate.

The difference last_valid - last_invalid precisely counts all valid starting positions for subarrays ending at the current index.

Because every subarray is counted exactly once, the algorithm is correct.

Python Solution

from typing import List

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        last_invalid = -1
        last_valid = -1
        total_subarrays = 0

        for index, value in enumerate(nums):
            if value > right:
                last_invalid = index

            if left <= value <= right:
                last_valid = index

            valid_count = last_valid - last_invalid

            if valid_count > 0:
                total_subarrays += valid_count

        return total_subarrays

The implementation follows the exact logic described in the algorithm walkthrough.

last_invalid tracks the most recent position where the element exceeded right. Any subarray crossing this index becomes invalid immediately.

last_valid tracks the most recent position where the element fell within the acceptable range. This ensures the subarray contains at least one value capable of being the maximum.

For every element, we compute:

last_valid - last_invalid

This gives the number of valid subarrays ending at the current position.

If this quantity is negative or zero, then no valid subarray ends here, so nothing is added.

The algorithm performs only one pass through the array and uses constant extra memory.

Go Solution

func numSubarrayBoundedMax(nums []int, left int, right int) int {
    lastInvalid := -1
    lastValid := -1
    totalSubarrays := 0

    for index, value := range nums {
        if value > right {
            lastInvalid = index
        }

        if value >= left && value <= right {
            lastValid = index
        }

        validCount := lastValid - lastInvalid

        if validCount > 0 {
            totalSubarrays += validCount
        }
    }

    return totalSubarrays
}

The Go implementation mirrors the Python solution closely.

Go slices are already dynamic references to arrays, so no special handling is needed for input storage.

The problem guarantees the final answer fits in a 32-bit integer, so using Go's standard int type is sufficient.

Unlike Python, Go requires explicit variable declarations and uses && instead of Python's chained comparisons.

Worked Examples

Example 1

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

Step-by-step Trace

Index	Value	last_invalid	last_valid	Valid Subarrays Ending Here	Running Total
0	2	-1	0	1	1
1	1	-1	0	1	2
2	4	2	0	0	2
3	3	2	3	1	3

Explanation

At index 0:

• 2 is within range
• Valid subarrays: [2]

At index 1:

• 1 is below left
• It extends previous valid subarrays
• Valid subarrays: [2,1]

At index 2:

• 4 > right
• Every subarray containing 4 becomes invalid

At index 3:

• 3 is valid
• Valid subarrays: [3]

Final answer:

3

Example 2

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

Step-by-step Trace

Index	Value	last_invalid	last_valid	Valid Subarrays Ending Here	Running Total
0	2	-1	0	1	1
1	9	1	0	0	1
2	2	1	2	1	2
3	5	1	3	2	4
4	6	1	4	3	7

Explanation

At index 1:

• 9 > right
• Any subarray containing 9 becomes invalid

At index 2:

• Valid subarray: [2]

At index 3:

• Valid subarrays:

• [5]

• [2,5]

At index 4:

• Valid subarrays:

• [6]

• [5,6]

• [2,5,6]

Final answer:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only a few integer variables are used

The algorithm processes each element exactly once. Every update and calculation is constant time, so the total runtime grows linearly with the array size.

No auxiliary data structures proportional to input size are required, so the extra space usage remains constant.

Test Cases

solution = Solution()

# Provided example 1
assert solution.numSubarrayBoundedMax([2,1,4,3], 2, 3) == 3

# Provided example 2
assert solution.numSubarrayBoundedMax([2,9,2,5,6], 2, 8) == 7

# Single valid element
assert solution.numSubarrayBoundedMax([5], 2, 8) == 1

# Single invalid element greater than right
assert solution.numSubarrayBoundedMax([10], 2, 8) == 0

# Single element below left
assert solution.numSubarrayBoundedMax([1], 2, 8) == 0

# All elements valid
assert solution.numSubarrayBoundedMax([2,3,4], 2, 4) == 6

# All elements too large
assert solution.numSubarrayBoundedMax([10,11,12], 2, 8) == 0

# All elements too small
assert solution.numSubarrayBoundedMax([0,0,0], 2, 8) == 0

# Mixed values with resets
assert solution.numSubarrayBoundedMax([2,1,5,2,3], 2, 3) == 5

# Large stretch of small values extending valid subarrays
assert solution.numSubarrayBoundedMax([2,1,1,1], 2, 3) == 4

# Multiple valid segments separated by invalid values
assert solution.numSubarrayBoundedMax([2,3,10,2,2], 2, 3) == 6

# left equals right
assert solution.numSubarrayBoundedMax([2,2,2], 2, 2) == 6

# Boundary values
assert solution.numSubarrayBoundedMax([0,1000000000], 0, 1000000000) == 3

Test Case Summary

Test	Why
[2,1,4,3]	Validates basic mixed behavior
[2,9,2,5,6]	Tests invalid reset logic
[5]	Single valid element
[10]	Single invalid element above range
[1]	Single element below range
[2,3,4]	Every subarray is valid
[10,11,12]	No valid subarrays
[0,0,0]	Values below left only
[2,1,5,2,3]	Multiple segments with resets
[2,1,1,1]	Small values extending validity
[2,3,10,2,2]	Invalid separator handling
[2,2,2]	Exact boundary matching
[0,1000000000]	Extreme constraint values

Edge Cases

Arrays Containing Values Greater Than right

Values greater than right are especially important because they invalidate every subarray containing them. A common bug is failing to fully reset counting logic after such an element appears.

For example:

nums = [2, 9, 2]

The value 9 splits the array into separate valid regions. The implementation handles this by updating last_invalid whenever a value exceeds right, ensuring no subarray crossing that index is counted.

Arrays Where Values Are Smaller Than left

Values below left cannot independently form valid subarrays, but they can extend existing valid ones.

For example:

nums = [2,1,1]

The subarrays [2,1] and [2,1,1] are still valid because the maximum remains 2.

A naive implementation may incorrectly discard these subarrays. The algorithm handles this correctly because last_valid remains unchanged until another in-range value appears.

Arrays With No Valid Elements

If every value is either below left or above right, the answer should be zero.

For example:

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

No subarray contains a maximum within the required range.

The implementation naturally handles this because last_valid never advances beyond last_invalid, so no valid subarrays are added.