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

// 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)
    

All Problems

All Solutions