Number of Subarrays With Bounded Maximum

Problem

Given an array and two integers left and right, count the number of contiguous subarrays whose maximum element lies between left and right, inclusive.

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

Python Solution

def num_subarray_bounded_max(nums, left, right):
    def count_at_most(bound):
        count = 0
        streak = 0
        for num in nums:
            streak = streak + 1 if num <= bound else 0
            count += streak
        return count

    return count_at_most(right) - count_at_most(left - 1)

C++ Solution

int countAtMost(vector<int>& nums, int bound) {
    int count = 0, streak = 0;
    for (int num : nums) {
        streak = (num <= bound) ? streak + 1 : 0;
        count += streak;
    }
    return count;
}

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

Java Solution

class Solution {
    private int countAtMost(int[] nums, int bound) {
        int count = 0, streak = 0;
        for (int num : nums) {
            streak = (num <= bound) ? streak + 1 : 0;
            count += streak;
        }
        return count;
    }

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

Complexity

Time: O(n) — two linear passes over the array. Space: O(1) — only a streak counter and running total. The atMost(bound) helper counts subarrays where every element is at most bound, using the fact that a valid streak of length L contributes L new subarrays ending at the current position.