Number of Subarrays with Bounded Maximum

Given an integer array nums and two integers left and right, return the number of contiguous subarrays where the maximum element is at least left and at most right.

This is LeetCode 795: Number of Subarrays with Bounded Maximum, and it is a great example of how tracking boundaries lets you count subarrays in linear time. Instead of checking every possible subarray, you sweep through once and use two pointer variables to determine exactly how many valid subarrays end at each index.

Why this problem matters

This problem teaches you a reusable counting technique for subarray problems. Many problems ask you to count subarrays satisfying some condition on the maximum, minimum, or sum. The brute-force approach of checking all O(n^2) subarrays is too slow. The technique here, counting valid subarrays ending at each position using boundary tracking, shows up repeatedly:

• Counting subarrays by contribution: instead of iterating over all subarrays, you ask "how many valid subarrays end at index i?" and sum the answers.
• Boundary variables: two integers (lastValid and lastInvalid) encode everything you need about the history of the array to the left of the current position.
• Single-pass thinking: you process each element once, update your state, and compute the contribution. No nested loops needed.

If you have practiced Subarray Product Less Than K, you have already seen a version of this counting pattern. This problem strips it down to its simplest form.

The key insight

For each index i, you want to know how many subarrays ending at i have their maximum in the range [left, right]. To answer this, you need two pieces of information:

1. Where is the last element that is too large? Any subarray that includes this element has a maximum exceeding right, so it is invalid. Call this position lastInvalid.
2. Where is the last element in range? A valid subarray must contain at least one element in [left, right] to guarantee the maximum is at least left. Call this position lastValid.

If lastValid > lastInvalid, then every subarray starting anywhere from lastInvalid + 1 to lastValid and ending at i is valid. That gives you lastValid - lastInvalid valid subarrays ending at i.

If lastValid <= lastInvalid, then no valid subarray ends at i, because the most recent "too large" element blocks any subarray that includes an in-range element.

Elements smaller than left do not update either pointer. They are harmless: they do not break validity (because the max is determined by larger elements) and they do not establish validity on their own (because a subarray of only too-small elements would have max below left).

The solution

def num_subarray_bounded_max(nums, left, right):
    count = 0
    last_valid = -1
    last_invalid = -1

    for i, num in enumerate(nums):
        if left <= num <= right:
            last_valid = i
        elif num > right:
            last_invalid = i

        if last_valid > last_invalid:
            count += last_valid - last_invalid

    return count

That is the entire solution. One pass through the array, two pointer variables, and an accumulator. Let's trace through it step by step.

Step-by-step walkthrough

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

The algorithm finds all 5 valid subarrays: [2], [2,1], [3], [3,2], and [2] (the last element). Notice how the 4 at index 2 acts as a wall. After that point, no valid subarray can reach back past it.

Complexity analysis

The boundary tracking approach processes each element exactly once. No extra data structures, no sorting, no hash maps. Just two integer variables and a running count.

The building blocks

This problem uses the linear scan with boundary tracking pattern. You walk through the array left to right, maintaining a small amount of state (two indices) that summarizes everything relevant about the elements you have already seen.

This same building block appears in other subarray counting problems:

• Subarray Product Less Than K: uses a sliding window to count subarrays where the product stays below a threshold. The counting technique (how many subarrays end at position i?) is identical.
• Maximum Subarray: Kadane's algorithm also sweeps left to right, maintaining running state. Instead of counting subarrays, it tracks the best sum ending at each position.
• Minimum Size Subarray Sum: another sliding window problem where you track boundaries to find the shortest valid subarray.

Once you see the shared structure, these problems become variations on a theme. The question is always: "what state do I need to carry forward, and how does the current element update it?"

Edge cases to watch for

• All elements in range: every subarray is valid. lastInvalid stays at -1, so count accumulates i + 1 at every step, giving n * (n + 1) / 2.
• All elements too large: lastValid stays at -1, which is never greater than lastInvalid. Count stays 0.
• All elements too small: lastValid stays at -1, lastInvalid stays at -1. Since lastValid is not greater than lastInvalid, count stays 0. No subarray has a max in range.
• Single element: if it is in [left, right], answer is 1. Otherwise, answer is 0.
• Alternating valid and invalid: the wall resets at each invalid element, and valid elements after it start fresh subarrays.

From understanding to recall

You can probably follow each step of this solution now. But could you write it from scratch tomorrow? In a week?

The gap between understanding and recall is real. This algorithm is only a few lines of code, but the logic behind the two pointers and the counting formula is easy to confuse with similar problems. Was it lastValid - lastInvalid or i - lastInvalid? Did you initialize to -1 or 0?

Spaced repetition closes that gap. You revisit this problem at increasing intervals, rewrite the solution from scratch each time, and after a few reps the boundary tracking pattern is locked in. The linear scan with boundary tracking pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Subarray Product Less Than K - Another subarray counting problem using a sliding window. Same core idea of counting subarrays ending at each position
• Maximum Subarray - Kadane's algorithm sweeps left to right with running state, the same single-pass structure
• Minimum Size Subarray Sum - Sliding window approach that tracks boundaries to find valid subarrays