795. Number of Subarrays with Bounded Maximum

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

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/
// Author: github.com/lzl124631x
// 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;
    }
};