## DEV Community is a community of 661,237 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Solution: Number of Subarrays with Bounded Maximum

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

We are given an array `nums` of positive integers, and two positive integers `left` and `right` (`left <= right`).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least `left` and at most `right`.

#### 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].

#### Constraints:

• `left`, `right`, and `nums[i]` will be an integer in the range `[0, 10^9]`.
• The length of `nums` will be in the range of `[1, 50000]`.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The key to this problem is realizing that we're dealing with overlapping triangular number issues. Importantly, the total number of possible subarrays that are contained within any larger subarray is the Nth triangular number, where N is the length of that larger subarray.

So the nums array starts with the (nums.length)th triangular number total subarrays. We want to exclude any subarray that includes a number larger than right, however. The easiest way to do this is to consider numbers larger than right to be dividers, splitting nums into many subarrays. We can add the triangular number for each of these resulting subarrays together to be the total number of subarrays that exclude numbers higher than right.

To do this, we can iterate through nums and keep track of how many contiguous numbers are less than right (mid) and each point that mid increments, we can add mid to ans, representing the increase to the next triangular number. The value for mid will then reset whenever we see a number higher than right.

But this only does half of the problem, because we still have to also exclude any subarray that does not have any number at least left high. To do this, we can use a similar method as for mid. We can keep track of how many contiguous numbers are lower than left (low) and decrease ans by that amount every time it increments, representing the next triangular number. Similar to mid, low will reset whenever we see a number at least left high.

Once we're done iterating, we can return ans.

Visual example:

• Time Complexity: O(N) where N is the length of nums
• Space Complexity: O(1)

#### Javascript Code:

``````var numSubarrayBoundedMax = function(nums, left, right) {
let ans = 0, low = 0, mid = 0
for (let i = 0; i < nums.length; i++) {
let num = nums[i]
if (num > right) mid = 0
else ans += ++mid
if (num >= left) low = 0
else ans -= ++low
}
return ans
};
``````

#### Python Code:

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

#### Java Code:

``````class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
int ans = 0, low = 0, mid = 0;
for (int num : nums) {
if (num > right) mid = 0;
else ans += ++mid;
if (num >= left) low = 0;
else ans -= ++low;
}
return ans;
}
}
``````

#### C++ Code:

``````class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int ans = 0, low = 0, mid = 0;
for (auto num : nums) {
if (num > right) mid = 0;
else ans += ++mid;
if (num >= left) low = 0;
else ans -= ++low;
}
return ans;
}
};
``````