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

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

############

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

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

############

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)

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

795 - Number of Subarrays with Bounded Maximum

795. Number of Subarrays with Bounded Maximum (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

795. Number of Subarrays with Bounded Maximum (Medium)

Solution 1.

All Problems

All Solutions