Domain 2MediumMEDIUM

Number of Subarrays with Bounded Maximum

Count subarrays with max in [L, R] by subtracting count of subarrays where all elements <= L-1 from those where all elements <= R.

Domain: medium•Updated: 2026-09-01
#complementary counting#linear scan#O(N)#O(1)

Problem Breakdown

We need to find the number of contiguous non-empty subarrays where every element is within a specific range relative to their maximum. Specifically, for a subarray sub, we require L≤max⁡(sub)≤RL \le \max(sub) \le R.

Inputs:

  • A: List of integers (array).
  • L, R: Integers defining the inclusive bounds (L≤RL \le R).

Outputs:

  • An integer representing the total valid subarrays found.

Constraints & Edge Cases:

  • Array length up to 50,000 (O(N)O(N) solution required; O(N2)O(N^2) will TLE).
  • Values can be large (10910^9), so we cannot use frequency arrays for values (only indices matter).
  • L <= R is guaranteed.
  • Subarrays must be non-empty and contiguous.

Intuition

A brute-force approach checking every subarray’s maximum would take O(N2)O(N^2) or worse, which exceeds time limits for N=50,000N=50,000. We need an efficient counting strategy.

Key Insight: Instead of directly counting valid ranges, we use complementary counting. A subarray satisfies the condition if:

  1. All its elements are ≤R\le R (ensures max <= R).
  2. It does not satisfy “all elements <L< L” (ensures at least one element ≥L\ge L, so max >= L).

Thus, Total Valid = (Count of subarrays where all elements <= R) - (Count of subarrays where all elements < L).

This transforms the problem into a simpler task: counting contiguous segments bounded by an upper limit. If we encounter an element greater than our current limit, that segment breaks (length resets to 0).

Approach

  1. Create a helper function count_le(limit) which returns the number of subarrays where every element is ≤\le limit.
  2. Inside this helper: Iterate through array A, maintaining a running length (current_len) of valid contiguous elements ending at current index. If an element exceeds limit, reset current_len to 0; otherwise, increment it and add it to the total count (since all subarrays ending here are valid).
  3. Call this helper twice: once with R and once with L - 1.
  4. Return the difference between these two counts.

Complexity Analysis

  • Time: O(N)O(N). We iterate through the array exactly twice (once for each limit), performing constant work per element. Total operations ≈2N\approx 2N.
  • Space: O(1)O(1) auxiliary space. We only use a few integer variables (count, current_len) regardless of input size.

Solution

def numSubarrayBoundedMax(A, L, R):
    def count_le(limit):
        """Counts subarrays where all elements are <= limit."""
        total = 0
        current_len = 0
        
        for x in A:
            if x <= limit:
                # Extend the valid window ending at this index
                current_len += 1
                # Add number of new valid subarrays ending here (length=1 to length=current_len)
                total += current_len 
            else:
                # Reset window as we encountered an invalid element
                current_len = 0
                
        return total

    # Count all subarrays with max <= R, minus those where max < L
    return count_le(R) - count_le(L - 1)

Edge Cases Handled

  • All elements > R: count_le(R) returns 0. Result is correct (0 valid).
  • L = 0 or negative: If limit passed to helper becomes -1, any non-negative integer in A will fail the check, correctly returning 0 for that part of calculation.
  • Empty Array: Constraints say length ≥\ge 1, but logic naturally handles empty input (loop doesn’t run, returns 0).
  • Large Values (10910^9): Python integers handle arbitrary size automatically; no overflow issues compared to fixed-width integer languages.