Formatted question description: https://leetcode.ca/all/795.html

# 795. Number of Subarrays with Bounded Maximum (Medium)

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :
Input:
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].


Note:

• L, R  and A[i] will be an integer in the range [0, 10^9].
• The length of A will be in the range of [1, 50000].

Companies:

Related Topics:
Array

## Solution 1.

Let’s pretend each element is either 0 if it is less than L; 1 if it is between L and R; or 2 if it is greater than R.

Since the subarray cannot contain 2, so we look for this pattern.

2 0 0 1 0 1 0 2


That is, a subarray surrounded by 2. We look within this subsequence.

There can be multiple 1s in the subarray. Now the question is: count subarrays that contain at least one 1.

In this solution, I choosed to look at the 1s one by one.

For the first 1:

       v
2) 0 0 1 0 1 0 (2


There are 2 zeros to its left, and 3 zero/ones to its right. So the count of subarray containing this 1 is (2 + 1) * (3 + 1) = 12.

Then for the next 1:

       x   v
2) 0 0 1 0 1 0 (2


To prevent recount the subarrays containing the first 1, we only look at the zeros to its left, and the count of which is 1. And there are 1 zero/ones to its right. So the count of subarray containing this second 1 but not the first 1 is (1 + 1) * (1 + 1) = 2.

So the answer should be 12 + 2 = 14.

// OJ: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int N = A.size(), begin = 0, maxVal = INT_MIN, cnt = 0;
while (begin < N) {
int end = begin;
while (end < N && A[end] <= R) {
maxVal = max(maxVal, A[end++]);
}
if (maxVal >= L) {
while (true) {
int i = begin;
while (i < end && A[i] < L) ++i;
if (i == end) break;
cnt += (i - begin + 1) * (end - i);
begin = i + 1;
}
}
begin = end + 1;
}
return cnt;
}
};


Java

• class Solution {
public int numSubarrayBoundedMax(int[] A, int L, int R) {
int count1 = 0, count2 = 0;
int curCount1 = 0, curCount2 = 0;
int length = A.length;
for (int i = 0; i < length; i++) {
int num = A[i];
if (num <= R)
curCount1++;
else {
count1 += curCount1 * (curCount1 + 1) / 2;
curCount1 = 0;
}
if (num < L)
curCount2++;
else {
count2 += curCount2 * (curCount2 + 1) / 2;
curCount2 = 0;
}
}
if (curCount1 > 0)
count1 += curCount1 * (curCount1 + 1) / 2;
if (curCount2 > 0)
count2 += curCount2 * (curCount2 + 1) / 2;
return count1 - count2;
}
}

• // OJ: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int left, int right) {
int N = A.size(), ans = 0;
for (int i = 0; i < N; ++i) {
if (A[i] > right) continue;
int last = -1, start = i;
for (; i < N && A[i] <= right; ++i) {
if (A[i] >= left && A[i] <= right) last = i;
if (last != -1) ans += last - start + 1;
}
}
return ans;
}
};

• class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
if not A: return 0
dp = [0] * len(A)
prev = -1
for i, a in enumerate(A):
if a < L and i > 0:
dp[i] = dp[i - 1]
elif a > R:
dp[i] = 0
prev = i
elif L <= a <= R:
dp[i] = i - prev
return sum(dp)