Problem Description

You are given an integer array nums and two integers left and right. A subarray of nums is a contiguous, non-empty sequence of elements within nums. The maximum of a subarray is the largest value present in that subarray.

Your task is to count the number of subarrays whose maximum element is at least left and at most right; in other words, the maximum lies in the interval [left, right].

• Each subarray must be contiguous.
• All possible subarrays must be considered.
• There is always at least one valid solution.
• You cannot reuse elements in a subarray, but subarrays can overlap in nums.

Constraints:

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

Thought Process

The most straightforward way to solve this problem is to consider every possible subarray, compute its maximum, and count it if the maximum is between left and right. However, this brute-force approach is not efficient for large arrays because it requires examining all O(n^2) subarrays.

To optimize, we can think about the properties of subarrays and how the maximum value changes as the subarray expands. Instead of checking each subarray individually, we can focus on efficiently counting subarrays that meet the maximum condition by leveraging the position of elements greater than right and those within [left, right].

The key insight is that any subarray that contains an element greater than right cannot be valid, so we can partition the array into blocks separated by such elements. Within each block, we can count subarrays whose maximum is at least left by counting those that contain at least one element in [left, right].

Solution Approach

Here is a step-by-step approach to solving the problem efficiently:

1. Partition the array: Treat every element greater than right as a boundary. Any subarray containing such an element cannot be valid. So, the array can be split into blocks of elements where all elements are less than or equal to right.
2. Count subarrays with a maximum at least left: For each block, we want to count the number of subarrays where the maximum is at least left. This is equivalent to counting all subarrays in the block, then subtracting those where all elements are less than left (i.e., the maximum is less than left).
3. Efficient counting: For each block:
   • Let the block have length len. The total number of subarrays is len * (len + 1) / 2.
   • To count subarrays where all elements are less than left, find all consecutive runs of elements less than left in the block. For each such run of length l, there are l * (l + 1) / 2 subarrays.
   • Subtract these from the total to get the count of valid subarrays in the block.
4. Iterate through the array: Use pointers or indices to keep track of boundaries and runs as you scan through nums once. This ensures an efficient O(n) solution.

This approach leverages the observation that the problem can be broken down into manageable segments, and counting is done mathematically rather than by enumeration.

Example Walkthrough

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

1. Identify elements greater than right (which is 3). The element 4 at index 2 is such a boundary.
2. The array is partitioned into two blocks:
   • Block 1: [2, 1]
   • Block 2: [3]
3. For Block 1 ([2, 1]):
   • Total subarrays: 2 (length) * 3 / 2 = 3 ([2], [1], [2,1])
   • Subarrays where all elements are less than 2: Only [1] (length 1 run). 1 * 2 / 2 = 1
   • Valid subarrays: 3 - 1 = 2 ([2], [2,1])
4. For Block 2 ([3]):
   • Total subarrays: 1 * 2 / 2 = 1 ([3])
   • All elements are at least 2, so no subarrays to subtract.
   • Valid subarrays: 1
5. Total valid subarrays: 2 (from Block 1) + 1 (from Block 2) = 3

Time and Space Complexity

• Brute-force approach:
  For every possible subarray (O(n²)), compute the maximum (up to O(n) per subarray), resulting in O(n³) time complexity. This is infeasible for large arrays.
• Optimized approach:
  The array is traversed once, and all counts are computed in a single pass using pointers and counters. This results in O(n) time complexity, where n is the length of nums.
  Space complexity is O(1), since only a few variables are used regardless of input size.

Summary

The key to solving the "Number of Subarrays with Bounded Maximum" problem efficiently is to recognize how elements greater than right partition the array and how to count valid subarrays mathematically within each partition. By subtracting subarrays whose maximum is less than left from all possible subarrays in each block, we avoid brute-force enumeration and achieve a linear-time solution. This approach is both elegant and highly efficient, suitable for large input sizes.

Code Implementation

class Solution:
    def numSubarrayBoundedMax(self, nums, left, right):
        def count(bound):
            ans = 0
            curr = 0
            for num in nums:
                if num <= bound:
                    curr += 1
                else:
                    curr = 0
                ans += curr
            return ans

        return count(right) - count(left - 1)
    

class Solution {
public:
    int count(vector<int>& nums, int bound) {
        int ans = 0, curr = 0;
        for (int num : nums) {
            if (num <= bound) {
                curr++;
            } else {
                curr = 0;
            }
            ans += curr;
        }
        return ans;
    }

    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }
};
    

class Solution {
    private int count(int[] nums, int bound) {
        int ans = 0, curr = 0;
        for (int num : nums) {
            if (num <= bound) {
                curr++;
            } else {
                curr = 0;
            }
            ans += curr;
        }
        return ans;
    }

    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }
}
    

var numSubarrayBoundedMax = function(nums, left, right) {
    function count(bound) {
        let ans = 0, curr = 0;
        for (let num of nums) {
            if (num <= bound) {
                curr++;
            } else {
                curr = 0;
            }
            ans += curr;
        }
        return ans;
    }
    return count(right) - count(left - 1);
};