Number of subarrays with maximum values in given range
Given an array of N elements and L and R, print the number of subarrays such that the value of the maximum array element in that subarray is at least L and at most R.
Examples:
Input : arr[] = {2, 0, 11, 3, 0} L = 1, R = 10 Output : 4 Explanation: the subarrays {2}, {2, 0}, {3} and {3, 0} have maximum in range 110. Input : arr[] = {3, 4, 1} L = 2, R = 4 Output : 5 Explanation: the subarrays are {3}, {4}, {3, 4}, {4, 1} and {3, 4, 1}
A naive approach will be to iterate for every subarray and find the number of subarrays with maximum in range LR. Time complexity of this solution is O(n*n)
An efficient approach is based on below facts :
 Any element > R is never included in any subarray.
 Any number of elements smaller than L can be included in subarray as long as there is at least one single element between L and R inclusive.
 The number of all possible subarrays of an array of size N is N * (N + 1)/2. Let countSubarrays(N) = N * (N + 1)/2
We keep track of two counts in current subarray.
1) Count of all elements smaller than or equal to R. We call it inc.
2) Count of all elements smaller than L. We call it exc.
Our answer for current subarray is countSubarrays(inc) – countSubarrays(exc). We basically remove all those subarrays which are formed by only elements smaller than L.
Below is the cpp implementation of the above approach

// CPP program to count subarrays whose maximum
// elements are in given range.
#include <bits/stdc++.h>
using
namespace
std;
// function to calculate N*(N+1)/2
long
countSubarrys(
long
n)
{
return
n * (n + 1) / 2;
}
// function to count the number of subarrays with
// maximum greater then L and less then R.
long
countSubarrays(
int
a[],
int
n,
int
L,
int
R)
{
long
res = 0;
// exc is going to store count of elements
// smaller than L in current valid subarray.
// inc is going to store count of elements
// smaller than or equal to R.
long
exc = 0, inc = 0;
// traverse through all elements of the array
for
(
int
i = 0; i < n; i++) {
// If the element is greater than R,
// add current value to result and reset
// values of exc and inc.
if
(a[i] > R) {
res += (countSubarrys(inc)  countSubarrys(exc));
inc = 0;
exc = 0;
}
// if it is less than L, then it is included
// in the subarrays
else
if
(a[i] < L) {
exc++;
inc++;
}
// if >= L and <= R, then count of
// subarrays formed by previous chunk
// of elements formed by only smaller
// elements is reduced from result.
else
{
res = countSubarrys(exc);
exc = 0;
inc++;
}
}
// Update result.
res += (countSubarrys(inc)  countSubarrys(exc));
// returns the count of subarrays
return
res;
}
// driver program
int
main()
{
int
a[] = { 2, 0, 11, 3, 0 };
int
n =
sizeof
(a) /
sizeof
(a[0]);
int
l = 1, r = 10;
cout << countSubarrays(a, n, l, r);
return
0;
}
Output:
4
Time Complexity: O(n)
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/numbersubarraysmaximumvaluegivenrange/
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide