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

Problem Statement

Given an integer array nums and integers left and right, return the number of contiguous subarrays where the max element is between left and right inclusive.

Input: nums=[2,1,4,3], left=2, right=3 → Output: 3

Intuition

Count subarrays with max ≤ R minus subarrays with max ≤ L-1. For "max ≤ X", count using consecutive valid elements: when nums[i] > X, reset count to 0.

Solutions

Python

def numSubarrayBoundedMax(nums: list[int], left: int, right: int) -> int:
    def count(bound):
        res = cur = 0
        for n in nums:
            cur = cur + 1 if n <= bound else 0
            res += cur
        return res
    return count(right) - count(left - 1)

C++

int numSubarrayBoundedMax(vector<int>& nums, int L, int R) {
    auto count=[&](int bound){
        int res=0,cur=0;
        for(int n:nums){cur=n<=bound?cur+1:0;res+=cur;}return res;};
    return count(R)-count(L-1);
}

JavaScript

var numSubarrayBoundedMax = function(nums, left, right) {
    const count = bound => {
        let res=0,cur=0;
        for(const n of nums){cur=n<=bound?cur+1:0;res+=cur;}return res;};
    return count(right)-count(left-1);
};

Complexity

Time: O(n)
Space: O(1)