795. Number of Subarrays with Bounded Maximum

1. Description

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays 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.

2. Example

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

3. Constraints

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

4. Solutions

Loop

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    // we want to count the range with at least one number in [left, right]
    // we get this value by [0, right] - [0, left]
    int numSubarrayBoundedMax(const vector<int> &nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }

    int count(const vector<int> &nums, int lower) {
        int result = 0, current_count = 0;
        for (auto num : nums) {
            current_count = num <= lower ? current_count + 1 : 0;
            result += current_count;
        }

        return result;
    }
};