Number of Subarrays with Bounded Maximum

Problem

Given an integer array nums and two integers left and right, return _the number of contiguous non-emptysubarrays such that the value of the maximum array element in that subarray is in the range _[left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

Examples

Example 1

    
    
    Input: nums = [2,1,4,3], left = 2, right = 3
    Output: 3
    Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
    

Example 2

    
    
    Input: nums = [2,9,2,5,6], left = 2, right = 8
    Output: 7
    

Constraints

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

Solution

Method 1 – Inclusion-Exclusion and Two Pointers

Intuition

The number of subarrays where the max is in [left, right] = (number of subarrays where max ≤ right) - (number of subarrays where max < left). We can count subarrays with max ≤ bound using a two-pointer approach.

Approach

1. Define a helper to count subarrays with all elements ≤ bound.
2. For each index, if nums[i] ≤ bound, increment count of valid subarrays ending at i; else reset count to 0.
3. Sum up the counts for all i.
4. The answer is count(right) - count(left-1).

Code

C++

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return count(nums, right) - count(nums, left-1);
    }
    int count(vector<int>& nums, int bound) {
        int ans = 0, cur = 0;
        for (int x : nums) {
            if (x <= bound) cur++;
            else cur = 0;
            ans += cur;
        }
        return ans;
    }
};

Go

func numSubarrayBoundedMax(nums []int, left, right int) int {
    return count(nums, right) - count(nums, left-1)
}
func count(nums []int, bound int) int {
    ans, cur := 0, 0
    for _, x := range nums {
        if x <= bound {
            cur++
        } else {
            cur = 0
        }
        ans += cur
    }
    return ans
}

Java

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return count(nums, right) - count(nums, left-1);
    }
    private int count(int[] nums, int bound) {
        int ans = 0, cur = 0;
        for (int x : nums) {
            if (x <= bound) cur++;
            else cur = 0;
            ans += cur;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun numSubarrayBoundedMax(nums: IntArray, left: Int, right: Int): Int {
        fun count(bound: Int): Int {
            var ans = 0
            var cur = 0
            for (x in nums) {
                if (x <= bound) cur++ else cur = 0
                ans += cur
            }
            return ans
        }
        return count(right) - count(left-1)
    }
}

Python

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

Rust

impl Solution {
    pub fn num_subarray_bounded_max(nums: Vec<i32>, left: i32, right: i32) -> i32 {
        fn count(nums: &Vec<i32>, bound: i32) -> i32 {
            let mut ans = 0;
            let mut cur = 0;
            for &x in nums {
                if x <= bound {
                    cur += 1;
                } else {
                    cur = 0;
                }
                ans += cur;
            }
            ans
        }
        count(&nums, right) - count(&nums, left-1)
    }
}

TypeScript

class Solution {
    numSubarrayBoundedMax(nums: number[], left: number, right: number): number {
        function count(bound: number): number {
            let ans = 0, cur = 0
            for (const x of nums) {
                if (x <= bound) cur++
                else cur = 0
                ans += cur
            }
            return ans
        }
        return count(right) - count(left-1)
    }
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)