Solution: Number of Subarrays with Bounded Maximum

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:

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

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

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

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

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