795. Number of Subarrays with Bounded Maximum

Description

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

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

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= left <= right <= 10⁹

Solutions

Solution 1: Direct Implementation

The question asks us to count the number of sub-arrays in the array nums whose maximum value is within the interval $[left, right]$.

For the interval $[left,..right]$ problem, we can consider the problem of converting it to $[0,..right]$ and then subtracting $[0,..left-1]$. That is to say, the number of all sub-arrays with the largest element not exceeding $right$ is subtracted from the number of all sub-arrays with the largest element not exceeding $left-1$. What remains is the number of sub-arrays with the largest element within the interval $[left,..right]$, which is the result required by the question.

\[ans = \sum_{i=0}^{right} ans_i - \sum_{i=0}^{left-1} ans_i\]

For this question, we design a function $f(x)$ to represent the number of sub-arrays in the array nums whose maximum value does not exceed $x$. Then the answer is $f(right) - f(left-1)$. The execution logic of function $f(x)$ is as follows:

Use variable $cnt$ to record the number of sub-arrays whose maximum value does not exceed $x$, and use $t$ to record the length of the current sub-array.
Traverse the array nums, for each element $nums[i]$, if $nums[i] \leq x$, then the length of the current subarray is increased by one, that is, $t=t+1$, otherwise the length of the current subarray is reset to 0, that is, $t=0$. Then add the length of the current subarray to $cnt$, which is $cnt = cnt + t$.
When the traversal is completed, return $cnt$.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Where $n$ is the length of the array nums.

Solution 2

We can also enumerate each element $nums[i]$ in the array as the maximum value of the subarray, and then count the number of subarrays with this element as the maximum value. The problem is transformed into finding the first subscript $l[i]$ on the left side of each element $nums[i]$ that is greater than the subscript $l[i]$ of the element, and the first subscript $r[i]$ on the right side greater than or equal to the element. Then the number of subarrays with this element as the maximum value is $(i - l[i]) \times (r[i] - i)$.

We can easily find $l[i]$ and $r[i]$ using a monotonic stack.

Time complexity $O(n)$, space complexity $O(n)$.

Similar topics:

907. Sum of minimum values of subarrays

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return f(nums, right) - f(nums, left - 1);
    }

    private int f(int[] nums, int x) {
        int cnt = 0, t = 0;
        for (int v : nums) {
            t = v > x ? 0 : t + 1;
            cnt += t;
        }
        return cnt;
    }
}


// Solution 2
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int n = nums.length;
        int[] l = new int[n];
        int[] r = new int[n];
        Arrays.fill(l, -1);
        Arrays.fill(r, n);
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            while (!stk.isEmpty() && nums[stk.peek()] <= v) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                l[i] = stk.peek();
            }
            stk.push(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; --i) {
            int v = nums[i];
            while (!stk.isEmpty() && nums[stk.peek()] < v) {
                stk.pop();
            }
            if (!stk.isEmpty()) {
                r[i] = stk.peek();
            }
            stk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left <= nums[i] && nums[i] <= right) {
                ans += (i - l[i]) * (r[i] - i);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        auto f = [&](int x) {
            int cnt = 0, t = 0;
            for (int& v : nums) {
                t = v > x ? 0 : t + 1;
                cnt += t;
            }
            return cnt;
        };
        return f(right) - f(left - 1);
    }
};


// Solution 2
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int n = nums.size();
        vector<int> l(n, -1);
        vector<int> r(n, n);
        stack<int> stk;
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            while (!stk.empty() && nums[stk.top()] <= v) stk.pop();
            if (!stk.empty()) l[i] = stk.top();
            stk.push(i);
        }
        stk = stack<int>();
        for (int i = n - 1; ~i; --i) {
            int v = nums[i];
            while (!stk.empty() && nums[stk.top()] < v) stk.pop();
            if (!stk.empty()) r[i] = stk.top();
            stk.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left <= nums[i] && nums[i] <= right) {
                ans += (i - l[i]) * (r[i] - i);
            }
        }
        return ans;
    }
};

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def f(x):
            cnt = t = 0
            for v in nums:
                t = 0 if v > x else t + 1
                cnt += t
            return cnt

        return f(right) - f(left - 1)


# Solution 2
class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        n = len(nums)
        l, r = [-1] * n, [n] * n
        stk = []
        for i, v in enumerate(nums):
            while stk and nums[stk[-1]] <= v:
                stk.pop()
            if stk:
                l[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] < nums[i]:
                stk.pop()
            if stk:
                r[i] = stk[-1]
            stk.append(i)
        return sum(
            (i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right
        )

func numSubarrayBoundedMax(nums []int, left int, right int) int {
	f := func(x int) (cnt int) {
		t := 0
		for _, v := range nums {
			t++
			if v > x {
				t = 0
			}
			cnt += t
		}
		return
	}
	return f(right) - f(left-1)
}


// Solution 2
func numSubarrayBoundedMax(nums []int, left int, right int) (ans int) {
	n := len(nums)
	l := make([]int, n)
	r := make([]int, n)
	for i := range l {
		l[i], r[i] = -1, n
	}
	stk := []int{}
	for i, v := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			l[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		v := nums[i]
		for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			r[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	for i, v := range nums {
		if left <= v && v <= right {
			ans += (i - l[i]) * (r[i] - i)
		}
	}
	return
}

795 - Number of Subarrays with Bounded Maximum

795. Number of Subarrays with Bounded Maximum

Description

Solutions

Solution 1: Direct Implementation

Solution 2

All Problems

All Solutions

Welcome to Subscribe On Youtube

795. Number of Subarrays with Bounded Maximum

Description

Solutions

Solution 1: Direct Implementation

Solution 2

All Problems

All Solutions