Number of subarrays with maximum values in given range
Given an array of N elements and L and R, print the number of sub-arrays 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 sub-arrays {2}, {2, 0}, {3} and {3, 0} have maximum in range 1-10. Input : arr[] = {3, 4, 1} L = 2, R = 4 Output : 5 Explanation: the sub-arrays are {3}, {4}, {3, 4}, {4, 1} and {3, 4, 1}
A naive approach will be to iterate for every sub-array and find the number of sub-arrays with the maximum in range L-R. The 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 the current subarray.
- Count of all elements smaller than or equal to R. We call it inc.
- 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 implementation of the above approach-
C++
// 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 sub-arrays with // maximum greater than L and less than 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 sub-arrays 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 sub-arrays 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; } |
Java
// Java program to count subarrays // whose maximum elements are // in given range. class GFG { // function to calculate N*(N+1)/2 static long countSubarrys( long n) { return n * (n + 1 ) / 2 ; } // function to count the number of // sub-arrays with maximum greater // then L and less than R. static 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 sub-arrays 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 sub-arrays return res; } // Driver code public static void main(String arg[]) { int a[] = { 2 , 0 , 11 , 3 , 0 }; int n = a.length; int l = 1 , r = 10 ; System.out.print(countSubarrays(a, n, l, r)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to count # subarrays whose maximum # elements are in given range. # function to calculate N*(N+1)/2 def countSubarrys(n): return n * (n + 1 ) / / 2 # function to count the # number of sub-arrays with # maximum greater than # L and less than R. def countSubarrays(a,n,L,R): 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. exc = 0 inc = 0 # traverse through all # elements of the array for i in range (n): # If the element is # greater than R, # add current value # to result and reset # values of exc and inc. if (a[i] > R): res = res + (countSubarrys(inc) - countSubarrys(exc)) inc = 0 exc = 0 # if it is less than L, # then it is included # in the sub-arrays elif (a[i] < L): exc = exc + 1 inc = inc + 1 # 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 = res - countSubarrys(exc) exc = 0 inc = inc + 1 # Update result. res = res + (countSubarrys(inc) - countSubarrys(exc)) # returns the count of sub-arrays return res # Driver code a = [ 2 , 0 , 11 , 3 , 0 ] n = len (a) l = 1 r = 10 print (countSubarrays(a, n, l, r)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to count subarrays // whose maximum elements are // in given range. using System; class GFG { // function to // calculate N*(N+1)/2 static long countSubarrys( long n) { return n * (n + 1) / 2; } // function to count the // number of sub-arrays // with maximum greater // then L and less than R. static 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 sub-arrays 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 sub-arrays return res; } // Driver code public static void Main() { int []a = {2, 0, 11, 3, 0}; int n = a.Length; int l = 1, r = 10; Console.WriteLine(countSubarrays(a, n, l, r)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count subarrays // whose maximum elements are in // given range. // function to calculate N*(N+1)/2 function countSubarrys( $n ) { return $n * ( $n + 1) / 2; } // function to count the number // of sub-arrays with maximum // greater than L and less than R. function countSubarrays( $a , $n , $L , $R ) { $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. $exc = 0; $inc = 0; // traverse through all // elements of the array for ( $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 sub-arrays 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 sub-arrays return $res ; } // Driver Code $a = array (2, 0, 11, 3, 0 ); $n = count ( $a ); $l = 1; $r = 10; echo countSubarrays( $a , $n , $l , $r ); // This code is contributed // by anuj_67. ?> |
Javascript
<script> // javascript program to count subarrays // whose maximum elements are // in given range. // function to calculate N*(N+1)/2 function countSubarrys(n) { return n * (n + 1) / 2; } // function to count the number of // sub-arrays with maximum greater // then L and less than R. function countSubarrays(a , n , L , R) { var 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. var exc = 0, inc = 0; // traverse through all elements of the array for (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 sub-arrays 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 sub-arrays return res; } // Driver code var a = [ 2, 0, 11, 3, 0 ]; var n = a.length; var l = 1, r = 10; document.write(countSubarrays(a, n, l, r)); // This code is contributed by todaysgaurav </script> |
Output:
4
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.