*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.*

####
Leetcode Problem #795 (*Medium*): Number of Subarrays with Bounded Maximum

####
*Description:*

*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:*

*Examples:*

Example 1: Input: nums = [2, 1, 4, 3]

left = 2

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

####
*Constraints:*

*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:*

*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 **N**th 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**.

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

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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;
}
};
```

## Top comments (0)