Number of Subarrays with Bounded Maximum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def count(bound):
            ans, cur = 0, 0
            for num in nums:
                cur = cur + 1 if num <= bound else 0
                ans += cur
            return ans

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

In this solution, we define a helper function count which counts the number of subarrays where the maximum element is less than or equal to its argument.

We then use this helper function to count the number of subarrays with maximum element less than or equal to right and subtract the count of subarrays with maximum element less than left - 1.

The result of this subtraction is the count of subarrays where the maximum element is in the range [left, right], which is the desired output.

This algorithm works because every subarray of the array nums is included exactly once in either count(right) or count(left - 1). Thus, subtracting these two counts gives the correct answer.