Number of Subarrays with Bounded Maximum | JS, Python, Java, C++ | Easy Triang. Number Sol. w/ Expl.
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe 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. \n\nSo 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**.\n\nTo 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**.\n\nBut 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.\n\nOnce we\'re done iterating, we can **return ans**.\n\nVisual example:\n![Visual 1](https://i.imgur.com/zr940xS.png)\n\n\n - _**Time Complexity: O(N)** where **N** is the length of **nums**_\n - _**Space Complexity: O(1)**_\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **72ms / 42.2MB** (beats 100% / 84%).\n```javascript\nvar numSubarrayBoundedMax = function(nums, left, right) {\n    let ans = 0, low = 0, mid = 0\n    for (let i = 0; i < nums.length; i++) {\n        let num = nums[i]\n        if (num > right) mid = 0\n        else ans += ++mid\n        if (num >= left) low = 0\n        else ans -= ++low\n    }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **316ms / 15.5MB** (beats 98% / 97%).\n```python\nclass Solution:\n    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n        ans, low, mid = 0, 0, 0\n        for num in nums:\n            if num > right: mid = 0\n            else:\n                mid += 1\n                ans += mid\n            if num >= left: low = 0\n            else:\n                low += 1\n                ans -= low\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **2ms / 46.8MB** (beats 100% / 75%).\n```java\nclass Solution {\n    public int numSubarrayBoundedMax(int[] nums, int left, int right) {\n        int ans = 0, low = 0, mid = 0;\n        for (int num : nums) {\n            if (num > right) mid = 0;\n            else ans += ++mid;\n            if (num >= left) low = 0;\n            else ans -= ++low;\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **24ms / 32.4MB** (beats 99% / 86%).\n```c++\nclass Solution {\npublic:\n    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {\n        int ans = 0, low = 0, mid = 0;\n        for (auto num : nums) {\n            if (num > right) mid = 0;\n            else ans += ++mid;\n            if (num >= left) low = 0;\n            else ans -= ++low;\n        }\n        return ans;\n    }\n};\n```
[]