Number of Subarrays with Bounded Maximum [Medium] — Counting Pattern

Problem Statement#

LeetCode 795 — Number of Subarrays with Bounded Maximum (Medium)

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the maximum element of the subarray is in the range [left, right] (inclusive).

Example 1:

Input:  nums = [2, 1, 4, 3], left = 2, right = 3
Output: 3
Explanation: Valid subarrays are [2], [2,1], [3]

Example 2:

Input:  nums = [2, 9, 2, 5, 6], left = 2, right = 8
Output: 7

Constraints:

• 1 <= nums.length <= 50,000
• 0 <= nums[i] <= 10^9
• 0 <= left <= right <= 10^9

Why This Problem Matters#

This problem is a classic example of a counting by complement technique. Instead of directly counting subarrays whose maximum falls in [left, right], you subtract two easier counts from each other. The same mathematical trick appears in dozens of interview problems across Amazon, Google, Meta, and Microsoft.

If you can articulate this decomposition clearly — and explain why it works — you immediately signal senior-level thinking to an interviewer. Beyond the trick itself, this problem teaches you how to count subarrays that satisfy a monotone predicate (like "max is at most X") in O(n) time using a running window count, which is a building block for more complex problems like Count Subarrays with Fixed Bounds (LC 2444) and Number of Subarrays with Bounded Maximum variants.

This is not a problem where brute force gets you through an interview. O(n^2) with a nested loop will time out on 50,000 elements. Knowing the O(n) insight cold is the goal.

The Counting Insight (count(max <= R) - count(max <= L-1))#

The Core Observation#

Counting subarrays whose max is exactly in [left, right] is hard directly. But counting subarrays whose max is at most some bound X is much easier. Notice:

subarrays with left <= max <= right
  = subarrays with max <= right
  - subarrays with max <= left - 1

This works because:

• "max <= right" includes all subarrays with max in [0, right].
• "max <= left - 1" includes all subarrays with max in [0, left - 1].
• Subtracting removes exactly the subarrays where max is too small, leaving only those where max is in [left, right].

This is a set difference argument. The two sets are nested (every subarray with max <= left-1 is also a subarray with max <= right), so subtraction is exact — no double counting.

How to Count "max at most X" in O(n)#

Now we need an efficient count(bound) function that returns the number of subarrays with max at most bound.

Key insight: A subarray has max at most bound if and only if every element in it is at most bound. So we just need to count contiguous runs of elements that are all <= bound.

For a contiguous run of length k, the number of subarrays is k * (k + 1) / 2. But instead of finding runs explicitly, we can use a running accumulator:

• Maintain cur = length of the current valid run ending at index i.
• If nums[i] <= bound, increment cur by 1.
• If nums[i] > bound, reset cur to 0 (the run is broken).
• Add cur to the result at each step.

Why does adding cur at each step work? Because cur tells you exactly how many subarrays end at index i and have all elements <= bound. Those subarrays start anywhere from index i - cur + 1 to index i.

For example, if the run so far is [2, 1, 3] at index 2 (all <= 5), then cur = 3 and those 3 subarrays are [3], [1,3], [2,1,3] — all ending at index 2. Adding 3 to the running total is exactly right.

Visual Dry Run (Step-by-Step Trace)#

Let's trace through nums = [2, 1, 4, 3], left = 2, right = 3.

We need count(right=3) - count(left-1=1).

Step 1: count(bound=3)#

count(3) = 4

The valid subarrays with max <= 3 are: [2], [2,1], [1], [3] — that's 4. Correct.

Step 2: count(bound=1)#

count(1) = 1

The only subarray with max <= 1 is: [1].

Final Answer#

count(3) - count(1) = 4 - 1 = 3

The 3 valid subarrays where max is in [2, 3] are: [2], [2,1], [3]. That matches the expected output.

Why [2,1] is valid but [2,1,4] is not#

[2,1] — max is 2, which is in [2,3]. Valid. [2,1,4] — max is 4, which is greater than 3. Invalid. [1] — max is 1, which is less than 2. Invalid (not in range).

The subtraction formula correctly removes [1] from the count.

Common Mistakes#

Mistake 1: Off-by-one in the lower bound#

The most frequent error is calling count(left) instead of count(left - 1). Remember:

• You want to exclude subarrays with max strictly less than left.
• Subarrays with max exactly equal to left should be included in the answer.
• count(left) would subtract too many subarrays (including those with max = left).
• count(left - 1) correctly excludes only those with max <= left - 1, i.e., max < left.

Always write the formula as: count(right) - count(left - 1).

Mistake 2: Forgetting to reset cur when the element exceeds the bound#

When nums[i] > bound, the current run of valid elements is broken. You must reset cur = 0, not just skip the element. If you skip without resetting, you carry forward a stale run length and overcount subarrays that span across an invalid element.

Wrong pattern:

# WRONG — does not reset cur
if nums[i] <= bound:
    cur += 1
    res += cur

Correct pattern:

# CORRECT — resets cur on invalid element
cur = cur + 1 if nums[i] <= bound else 0
res += cur

Mistake 3: Trying to count the valid range directly without decomposition#

A common brute-force instinct is to scan with two pointers or nested loops, keeping track of the current max. This leads to O(n^2) or O(n log n) solutions. The key insight — decompose into two simpler "at most" counts — reduces this to two O(n) passes. Always look for this decomposition pattern when asked to count subarrays/substrings with a condition on an extremal value (min or max).

Mistake 4: Assuming the answer is symmetric in left and right#

The subtraction is not count(right) - count(left). It is count(right) - count(left - 1). These are different. If left = right = X, the answer should be the count of subarrays with max exactly X. That requires count(X) - count(X - 1), not count(X) - count(X) (which would always be 0).

Mistake 5: Integer overflow concern (in other languages)#

In Python this is not an issue because integers are arbitrary precision. But in interviews where the language might matter, note that nums.length can be 50,000 and the answer can be as large as 50000 * 50001 / 2 ≈ 1.25 * 10^9, which fits in a 32-bit signed integer but just barely. If the interviewer asks you to switch to a language with fixed-size integers, use 64-bit (long/int64).

Solutions#

Python Solution#

def numSubarrayBoundedMax(nums: list[int], left: int, right: int) -> int:
    def count(bound: int) -> int:
        """
        Count subarrays where every element is <= bound.
        Equivalently: subarrays with max <= bound.
        """
        res = 0   # total count of valid subarrays
        cur = 0   # length of current valid run ending at this index
 
        for n in nums:
            # If this element is within bound, extend the current run.
            # If it exceeds the bound, the run is broken — reset to 0.
            cur = cur + 1 if n <= bound else 0
 
            # cur tells us how many subarrays end here with all elements <= bound.
            # Add them all to the result.
            res += cur
 
        return res
 
    # Subarrays with left <= max <= right
    # = subarrays with max <= right
    # - subarrays with max <= left - 1
    return count(right) - count(left - 1)

JavaScript Solution#

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var numSubarrayBoundedMax = function(nums, left, right) {
 
    /**
     * Count subarrays where every element is <= bound.
     * Uses a running "valid run length" accumulator.
     * @param {number} bound
     * @return {number}
     */
    function count(bound) {
        let res = 0;  // total count of valid subarrays found so far
        let cur = 0;  // length of the current run of elements all <= bound
 
        for (const n of nums) {
            // Extend the run if this element is within bound.
            // Break (reset) the run if it exceeds the bound.
            cur = n <= bound ? cur + 1 : 0;
 
            // Every position in the current run is a valid start for a
            // subarray ending at this index, so add cur to the total.
            res += cur;
        }
 
        return res;
    }
 
    // Apply the complement formula:
    // count(left <= max <= right) = count(max <= right) - count(max <= left - 1)
    return count(right) - count(left - 1);
};

Complexity Analysis#

The optimal solution makes exactly two linear passes over nums — one for count(right) and one for count(left - 1) — and uses only two integer variables in each pass. This is as good as it gets: O(n) time, O(1) space.

Follow-up Questions#

These are real follow-up questions interviewers at FAANG companies ask after you solve the base problem:

Q1: Can you solve it in a single pass instead of two?

Yes. Instead of calling count twice, you can maintain two running accumulators — one for "right bound" and one for "left-1 bound" — simultaneously. Update both in a single loop. The answer is the difference of the two accumulators at the end. This reduces constant factors but doesn't change the asymptotic complexity.

Q2: What if instead of the maximum we wanted the minimum to be in [left, right]?

The same subtraction formula applies: countMin(right) - countMin(left - 1), where countMin(bound) counts subarrays with minimum <= bound. The implementation is identical except you check n >= bound (not n <= bound) when deciding whether the element extends a valid run — actually, counting subarrays with min at most bound is the same structure. Think it through carefully: a subarray has min >= left iff every element is >= left. You would adapt the count helper accordingly.

Q3: What if the array can have negative numbers?

The algorithm as written works for any integers (including negatives) as long as left and right are also integers. The subtraction formula and the running accumulator don't assume non-negativity. No code change is needed.

Q4: LC 2444 — Count Subarrays with Fixed Bounds. How does this relate?

LC 2444 asks for subarrays where both the minimum equals minK and the maximum equals maxK. It is significantly harder — it requires tracking the last positions where the min and max conditions were satisfied simultaneously, plus a "killer" position for out-of-range elements. The counting insight from LC 795 is a prerequisite building block, but the implementation is more involved.

Q5: Can you extend this to count subarrays where the k-th largest element is in [left, right]?

This is a harder problem. You can combine a monotonic data structure (like a sorted list or a max-heap maintained over a sliding window) with the subtraction idea. The count helper becomes O(n log n) instead of O(n), making the overall complexity O(n log n).

This Pattern Solves#

The "count(at most X) minus count(at most Y)" decomposition is broadly applicable. Recognize it whenever a problem asks you to count subarrays (or substrings, or subsequences) where some aggregate over the subarray falls in a range [L, R]:

• LC 713 — Subarray Product Less Than K: Count subarrays with product < k. One bound only, but same running-window idea.
• LC 2444 — Count Subarrays with Fixed Bounds: Max = maxK and min = minK simultaneously.
• LC 1343 — Number of Subarrays of Size K and Average >= Threshold: Fixed-size window variant.
• LC 2302 — Count Subarrays with Score Less Than K: Score defined as sum * length.
• Counting subarrays with sum in [L, R]: Use prefix sums + sorted structure, but the complement idea applies.

Any time a predicate is monotone — if a subarray satisfies it, all sub-subarrays do too — the "at most" count with a running accumulator is a candidate.

Key Takeaways#

• The key formula: count(max in [L, R]) = count(max <= R) - count(max <= L-1). The L-1 (not L) is critical — you want to exclude elements strictly less than L.
• The count(max <= bound) helper uses a running cur accumulator: reset to 0 when nums[i] > bound, otherwise cur += 1 (add the number of new valid subarrays ending at i).
• O(n) time, O(1) space — two linear passes using the same helper function.
• This "difference of at-most counts" technique works whenever the predicate is monotone: if a subarray passes, all sub-subarrays do too (for max-bounded predicates).
• The same technique applies to LC 992 (Subarrays with K Different Integers), LC 713 (Product Less Than K), and LC 2444 (Count Subarrays with Fixed Bounds).
• Reset cur = 0 (not decrement) when the current element exceeds the bound — it breaks all valid subarrays ending here.
• Interviewers test this to see if you recognize that "exactly in range" = "at most upper" minus "at most lower-1" — a standard combinatorics trick applied to subarrays.