Solution: Number of Subarrays with Bounded Maximum
Tags: algorithms, javascript, java, python
Published: 2021-06-17 09:20:40

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/discuss/1278426).*

---

#### [Leetcode Problem #795 (*Medium*): Number of Subarrays with Bounded Maximum](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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]<br>left = 2<br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

Visual example:
![Visual 1](https://i.imgur.com/zr940xS.png)


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

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```