Count subarrays for every array element in which they are the minimum
Given an array arr[] consisting of N integers, the task is to create an array brr[] of size N where brr[i] represents the count of subarrays in which arr[i] is the smallest element.
Examples:
Input: arr[] = {3, 2, 4}
Output: {1, 3, 1}
Explanation:
For arr[0], there is only one subarray in which 3 is the smallest({3}).
For arr[1], there are three such subarrays where 2 is the smallest({2}, {3, 2}, {2, 4}).
For arr[2], there is only one subarray in which 4 is the smallest({4}).Input: arr[] = {1, 2, 3, 4, 5}
Output: {5, 4, 3, 2, 1}
Naive Approach: The simplest approach is to generate all subarrays of the given array and while generating the subarray, find the element which is minimum in that subarray and then store the index of that element, then later increment count for that index by 1. Similarly, do this for every subarray
Code-
C++
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count subarrays for every array element in //which they are minimum vector< int > countingSubarray(vector< int > arr, int n) { vector< int > ans(n,0); for ( int i=0;i<n;i++){ int temp=i; for ( int j=i;j<n;j++){ if (arr[j]<arr[temp]){temp=j;} ans[temp]++; } } return ans; } // Driver Code int main() { int N = 5; // Given array arr[] vector< int > arr = { 3, 2, 4, 1, 5 }; // Function call auto a = countingSubarray(arr, N); cout << "[" ; int n = a.size() - 1; for ( int i = 0; i < n; i++) cout << a[i] << ", " ; cout << a[n] << "]" ; return 0; } |
Java
import java.util.*; class Main { // Function to count subarrays for every array element in // which they are minimum static List<Integer> countingSubarray(List<Integer> arr, int n) { List<Integer> ans = new ArrayList<>(Collections.nCopies(n, 0 )); for ( int i = 0 ; i < n; i++) { int temp = i; for ( int j = i; j < n; j++) { if (arr.get(j) < arr.get(temp)) { temp = j; } ans.set(temp, ans.get(temp) + 1 ); } } return ans; } // Driver Code public static void main(String[] args) { int N = 5 ; // Given array arr[] List<Integer> arr = Arrays.asList( 3 , 2 , 4 , 1 , 5 ); // Function call List<Integer> a = countingSubarray(arr, N); System.out.print( "[" ); int n = a.size() - 1 ; for ( int i = 0 ; i < n; i++) { System.out.print(a.get(i) + ", " ); } System.out.println(a.get(n) + "]" ); } } |
Python3
# Python code addition # Function to count subarrays for every array element in # which they are minimum def countingSubarray(arr, n): ans = [ 0 ] * n for i in range (n): temp = i for j in range (i, n): if arr[j] < arr[temp]: temp = j ans[temp] + = 1 return ans # Driver Code N = 5 # Given array arr[] arr = [ 3 , 2 , 4 , 1 , 5 ] # Function call a = countingSubarray(arr, N) print (a) # The code is contributed by Arushi Goel. |
C#
using System; using System.Collections.Generic; class Program { // Function to count subarrays for every array element in // which they are minimum static List< int > CountingSubarray(List< int > arr, int n) { List< int > ans = new List< int >( new int [n]); for ( int i = 0; i < n; i++) { int temp = i; for ( int j = i; j < n; j++) { if (arr[j] < arr[temp]) temp = j; ans[temp]++; } } return ans; } static void Main() { int N = 5; // Given array arr[] List< int > arr = new List< int > { 3, 2, 4, 1, 5 }; // Function call List< int > a = CountingSubarray(arr, N); Console.Write( "[" ); int n = a.Count - 1; for ( int i = 0; i < n; i++) { Console.Write(a[i] + ", " ); } Console.Write(a[n] + "]" ); } } |
Javascript
// Javascript code addition // Function to count subarrays for every array element in // which they are minimum function countingSubarray(arr, n) { let ans = new Array(n).fill(0); for (let i = 0; i < n; i++) { let temp = i; for (let j = i; j < n; j++) { if (arr[j] < arr[temp]) { temp = j; } ans[temp]++; } } return ans; } // Driver Code let N = 5; // Given array arr[] let arr = [3, 2, 4, 1, 5]; // Function call let a = countingSubarray(arr, N); console.log(a); // The code is contributed by Arushi Goel. |
[1, 4, 1, 8, 1]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to find the boundary index for every element, up to which it is the smallest element. For each element let L and R be the boundary indices on the left and right side respectively up to which arr[i] is the minimum. Therefore, the count of all subarrays can be calculated by:
(L + R + 1)*(R + 1)
Follow the steps below to solve the problem:
- Store all the indices of array elements in a Map.
- Sort the array in increasing order.
- Initialize an array boundary[].
- Iterate over the sorted array arr[] and simply insert the index of that element using Binary Search. Suppose it got inserted at index i, then its left boundary is boundary[i – 1] and its right boundary is boundary[i + 1].
- Now, using the above formula, find the number of subarrays and keep track of that count in the resultant array.
- After completing the above steps, print all the counts stored in the resultant array.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the boundary of every // element within which it is minimum int binaryInsert(vector< int > &boundary, int i) { int l = 0; int r = boundary.size() - 1; // Perform Binary Search while (l <= r) { // Find mid m int m = (l + r) / 2; // Update l if (boundary[m] < i) l = m + 1; // Update r else r = m - 1; } // Inserting the index boundary.insert(boundary.begin() + l, i); return l; } // Function to required count subarrays vector< int > countingSubarray(vector< int > arr, int n) { // Stores the indices of element unordered_map< int , int > index; for ( int i = 0; i < n; i++) index[arr[i]] = i; vector< int > boundary = {-1, n}; sort(arr.begin(), arr.end()); // Initialize the output array vector< int > ans(n, 0); for ( int num : arr) { int i = binaryInsert(boundary, index[num]); // Left boundary, till the // element is smallest int l = boundary[i] - boundary[i - 1] - 1; // Right boundary, till the // element is smallest int r = boundary[i + 1] - boundary[i] - 1; // Calculate the number of subarrays // based on its boundary int cnt = l + r + l * r + 1; // Adding cnt to the ans ans[index[num]] += cnt; } return ans; } // Driver Code int main() { int N = 5; // Given array arr[] vector< int > arr = { 3, 2, 4, 1, 5 }; // Function call auto a = countingSubarray(arr, N); cout << "[" ; int n = a.size() - 1; for ( int i = 0; i < n; i++) cout << a[i] << ", " ; cout << a[n] << "]" ; return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the boundary of every // element within which it is minimum static int binaryInsert(ArrayList<Integer> boundary, int i) { int l = 0 ; int r = boundary.size() - 1 ; // Perform Binary Search while (l <= r) { // Find mid m int m = (l + r) / 2 ; // Update l if (boundary.get(m) < i) l = m + 1 ; // Update r else r = m - 1 ; } // Inserting the index boundary.add(l, i); return l; } // Function to required count subarrays static int [] countingSubarray( int [] arr, int n) { // Stores the indices of element Map<Integer, Integer> index = new HashMap<>(); for ( int i = 0 ; i < n; i++) index.put(arr[i], i); ArrayList<Integer> boundary = new ArrayList<>(); boundary.add(- 1 ); boundary.add(n); Arrays.sort(arr); // Initialize the output array int [] ans = new int [n]; for ( int num : arr) { int i = binaryInsert(boundary, index.get(num)); // Left boundary, till the // element is smallest int l = boundary.get(i) - boundary.get(i - 1 ) - 1 ; // Right boundary, till the // element is smallest int r = boundary.get(i + 1 ) - boundary.get(i) - 1 ; // Calculate the number of subarrays // based on its boundary int cnt = l + r + l * r + 1 ; // Adding cnt to the ans ans[index.get(num)] += cnt; } return ans; } // Driver code public static void main (String[] args) { int N = 5 ; // Given array arr[] int [] arr = { 3 , 2 , 4 , 1 , 5 }; // Function call int [] a = countingSubarray(arr, N); System.out.print( "[" ); int n = a.length - 1 ; for ( int i = 0 ; i < n; i++) System.out.print(a[i] + ", " ); System.out.print(a[n] + "]" ); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the boundary of every # element within which it is minimum def binaryInsert(boundary, i): l = 0 r = len (boundary) - 1 # Perform Binary Search while l < = r: # Find mid m m = (l + r) / / 2 # Update l if boundary[m] < i: l = m + 1 # Update r else : r = m - 1 # Inserting the index boundary.insert(l, i) return l # Function to required count subarrays def countingSubarray(arr, n): # Stores the indices of element index = {} for i in range (n): index[arr[i]] = i boundary = [ - 1 , n] arr.sort() # Initialize the output array ans = [ 0 for i in range (n)] for num in arr: i = binaryInsert(boundary, index[num]) # Left boundary, till the # element is smallest l = boundary[i] - boundary[i - 1 ] - 1 # Right boundary, till the # element is smallest r = boundary[i + 1 ] - boundary[i] - 1 # Calculate the number of subarrays # based on its boundary cnt = l + r + l * r + 1 # Adding cnt to the ans ans[index[num]] + = cnt return ans # Driver Code N = 5 # Given array arr[] arr = [ 3 , 2 , 4 , 1 , 5 ] # Function Call print (countingSubarray(arr, N)) |
C#
// C# program for // the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to find the // boundary of every element // within which it is minimum static int binaryInsert(ArrayList boundary, int i) { int l = 0; int r = boundary.Count - 1; // Perform Binary Search while (l <= r) { // Find mid m int m = (l + r) / 2; // Update l if (( int )boundary[m] < i) l = m + 1; // Update r else r = m - 1; } // Inserting the index boundary.Insert(l, i); return l; } // Function to required count subarrays static int [] countingSubarray( int [] arr, int n) { // Stores the indices of element Dictionary< int , int > index = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) index[arr[i]] = i; ArrayList boundary = new ArrayList(); boundary.Add(-1); boundary.Add(n); Array.Sort(arr); // Initialize the output array int [] ans = new int [n]; foreach ( int num in arr) { int i = binaryInsert(boundary, index[num]); // Left boundary, till the // element is smallest int l = ( int )boundary[i] - ( int )boundary[i - 1] - 1; // Right boundary, till the // element is smallest int r = ( int )boundary[i + 1] - ( int )boundary[i] - 1; // Calculate the number of // subarrays based on its boundary int cnt = l + r + l * r + 1; // Adding cnt to the ans ans[index[num]] += cnt; } return ans; } // Driver code public static void Main( string [] args) { int N = 5; // Given array arr[] int [] arr = {3, 2, 4, 1, 5}; // Function call int [] a = countingSubarray(arr, N); Console.Write( "[" ); int n = a.Length - 1; for ( int i = 0; i < n; i++) Console.Write(a[i] + ", " ); Console.Write(a[n] + "]" ); } } // This code is contributed by Rutvik_56 |
Javascript
<script> // JavaScript program for the above approach // Function to find the boundary of every // element within which it is minimum function binaryInsert(boundary, i){ let l = 0 let r = boundary.length - 1 // Perform Binary Search while (l <= r){ // Find mid m let m = Math.floor((l + r) / 2) // Update l if (boundary[m] < i) l = m + 1 // Update r else r = m - 1 } // Inserting the index boundary.splice(l,0, i) return l } // Function to required count subarrays function countingSubarray(arr, n){ // Stores the indices of element let index = new Map() for (let i=0;i<n;i++) index.set(arr[i] , i) let boundary = [-1, n] arr.sort() // Initialize the output array let ans = new Array(n).fill(0) for (let num of arr){ let i = binaryInsert(boundary, index.get(num)) // Left boundary, till the // element is smallest let l = boundary[i] - boundary[i - 1] - 1 // Right boundary, till the // element is smallest let r = boundary[i + 1] - boundary[i] - 1 // Calculate the number of subarrays // based on its boundary let cnt = l + r + l * r + 1 // Adding cnt to the ans ans[index.get(num)] += cnt } return ans } // Driver Code let N = 5 // Given array arr[] let arr = [3, 2, 4, 1, 5] // Function Call document.write(countingSubarray(arr, N), "</br>" ) // This code is contributed by shinjanpatra. </script> |
[1, 4, 1, 8, 1]
Time Complexity: O(N log N)
Auxiliary Space: O(N)
Most efficient approach:
To optimize the above approach we can use a Stack Data Structure.
- Idea is that, For each (1? i ? N) we will try to find index(R) of next smaller element right to it and index(L) of next smaller element left to it.
- Now we have our boundary index(L,R) in which arr[i] is minimum so total number of subarrays for each i(0-base) will be (R-i)*(i-L) .
Below is the implementation of the idea:
C++14
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to required count subarrays vector< int > countingSubarray(vector< int > arr, int n) { // For storing count of subarrays vector< int > a(n); // For finding next smaller // element left to a element // if there is no next smaller // element left to it than taking -1. vector< int > nsml(n, -1); // For finding next smaller // element right to a element // if there is no next smaller // element right to it than taking n. vector< int > nsmr(n, n); stack< int > st; for ( int i = n - 1; i >= 0; i--) { while (!st.empty() && arr[st.top()] >= arr[i]) st.pop(); nsmr[i] = (!st.empty()) ? st.top() : n; st.push(i); } while (!st.empty()) st.pop(); for ( int i = 0; i < n; i++) { while (!st.empty() && arr[st.top()] >= arr[i]) st.pop(); nsml[i] = (!st.empty()) ? st.top() : -1; st.push(i); } for ( int i = 0; i < n; i++) { // Taking exact boundaries // in which arr[i] is // minimum nsml[i]++; // Similarly for right side nsmr[i]--; int r = nsmr[i] - i + 1; int l = i - nsml[i] + 1; a[i] = r * l; } return a; } // Driver Code int main() { int N = 5; // Given array arr[] vector< int > arr = { 3, 2, 4, 1, 5 }; // Function call auto a = countingSubarray(arr, N); cout << "[" ; int n = a.size() - 1; for ( int i = 0; i < n; i++) cout << a[i] << ", " ; cout << a[n] << "]" ; return 0; } |
Java
// Java implementation of the above approach import java.util.*; public class gfg { // Function to required count subarrays static int [] countingSubarray( int arr[], int n) { // For storing count of subarrays int a[] = new int [n]; // For finding next smaller // element left to a element // if there is no next smaller // element left to it than taking -1. int nsml[] = new int [n]; Arrays.fill(nsml, - 1 ); // For finding next smaller // element right to a element // if there is no next smaller // element right to it than taking n. int nsmr[] = new int [n]; Arrays.fill(nsmr, n); Stack<Integer> st = new Stack<Integer>(); for ( int i = n - 1 ; i >= 0 ; i--) { while (st.size() > 0 && arr[( int )st.peek()] >= arr[i]) st.pop(); nsmr[i] = (st.size() > 0 ) ? ( int )st.peek() : n; st.push(i); } while (st.size() > 0 ) st.pop(); for ( int i = 0 ; i < n; i++) { while (st.size() > 0 && arr[( int )st.peek()] >= arr[i]) st.pop(); nsml[i] = (st.size() > 0 ) ? ( int )st.peek() : - 1 ; st.push(i); } for ( int i = 0 ; i < n; i++) { // Taking exact boundaries // in which arr[i] is // minimum nsml[i]++; // Similarly for right side nsmr[i]--; int r = nsmr[i] - i + 1 ; int l = i - nsml[i] + 1 ; a[i] = r * l; } return a; } // Driver code public static void main(String[] args) { int N = 5 ; // Given array arr[] int arr[] = { 3 , 2 , 4 , 1 , 5 }; // Function call int a[] = countingSubarray(arr, N); System.out.print( "[" ); int n = a.length - 1 ; for ( int i = 0 ; i < n; i++) System.out.print(a[i] + ", " ); System.out.print(a[n] + "]" ); } } // This code is contributed by divyesh072019. |
Python3
# Python implementation of the above approach # Function to required count subarrays def countingSubarray(arr, n): # For storing count of subarrays a = [ 0 for i in range (n)] # For finding next smaller # element left to a element # if there is no next smaller # element left to it than taking -1. nsml = [ - 1 for i in range (n)] # For finding next smaller # element right to a element # if there is no next smaller # element right to it than taking n. nsmr = [n for i in range (n)] st = [] for i in range (n - 1 , - 1 , - 1 ): while ( len (st) > 0 and arr[st[ - 1 ]] > = arr[i]): del st[ - 1 ] if ( len (st) > 0 ): nsmr[i] = st[ - 1 ] else : nsmr[i] = n st.append(i) while ( len (st) > 0 ): del st[ - 1 ] for i in range (n): while ( len (st) > 0 and arr[st[ - 1 ]] > = arr[i]): del st[ - 1 ] if ( len (st) > 0 ): nsml[i] = st[ - 1 ] else : nsml[i] = - 1 st.append(i) for i in range (n): # Taking exact boundaries # in which arr[i] is # minimum nsml[i] + = 1 # Similarly for right side nsmr[i] - = 1 r = nsmr[i] - i + 1 ; l = i - nsml[i] + 1 ; a[i] = r * l; return a; # Driver code N = 5 # Given array arr[] arr = [ 3 , 2 , 4 , 1 , 5 ] # Function call a = countingSubarray(arr, N) print (a) # This code is contributed by rag2127 |
C#
// C# implementation of the above approach using System; using System.Collections; class GFG{ // Function to required count subarrays static int [] countingSubarray( int [] arr, int n) { // For storing count of subarrays int [] a = new int [n]; // For finding next smaller // element left to a element // if there is no next smaller // element left to it than taking -1. int [] nsml = new int [n]; Array.Fill(nsml, -1); // For finding next smaller // element right to a element // if there is no next smaller // element right to it than taking n. int [] nsmr = new int [n]; Array.Fill(nsmr, n); Stack st = new Stack(); for ( int i = n - 1; i >= 0; i--) { while (st.Count > 0 && arr[( int )st.Peek()] >= arr[i]) st.Pop(); nsmr[i] = (st.Count > 0) ? ( int )st.Peek() : n; st.Push(i); } while (st.Count > 0) st.Pop(); for ( int i = 0; i < n; i++) { while (st.Count > 0 && arr[( int )st.Peek()] >= arr[i]) st.Pop(); nsml[i] = (st.Count > 0) ? ( int )st.Peek() : -1; st.Push(i); } for ( int i = 0; i < n; i++) { // Taking exact boundaries // in which arr[i] is // minimum nsml[i]++; // Similarly for right side nsmr[i]--; int r = nsmr[i] - i + 1; int l = i - nsml[i] + 1; a[i] = r * l; } return a; } // Driver code static void Main() { int N = 5; // Given array arr[] int [] arr = { 3, 2, 4, 1, 5 }; // Function call int [] a = countingSubarray(arr, N); Console.Write( "[" ); int n = a.Length - 1; for ( int i = 0; i < n; i++) Console.Write(a[i] + ", " ); Console.Write(a[n] + "]" ); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript implementation of the above approach // Function to required count subarrays function countingSubarray(arr, n) { // For storing count of subarrays let a = new Array(n); // For finding next smaller // element left to a element // if there is no next smaller // element left to it than taking -1. let nsml = new Array(n); nsml.fill(-1); // For finding next smaller // element right to a element // if there is no next smaller // element right to it than taking n. let nsmr = new Array(n); nsmr.fill(n); let st = []; for (let i = n - 1; i >= 0; i--) { while (st.length > 0 && arr[st[st.length-1]] >= arr[i]) st.pop(); nsmr[i] = (st.length > 0) ? st[st.length-1] : n; st.push(i); } while (st.length > 0) st.pop(); for (let i = 0; i < n; i++) { while (st.length > 0 && arr[st[st.length-1]] >= arr[i]) st.pop(); nsml[i] = (st.length > 0) ? st[st.length-1] : -1; st.push(i); } for (let i = 0; i < n; i++) { // Taking exact boundaries // in which arr[i] is // minimum nsml[i]++; // Similarly for right side nsmr[i]--; let r = nsmr[i] - i + 1; let l = i - nsml[i] + 1; a[i] = r * l; } return a; } let N = 5; // Given array arr[] let arr = [ 3, 2, 4, 1, 5 ]; // Function call let a = countingSubarray(arr, N); document.write( "[" ); let n = a.length - 1; for (let i = 0; i < n; i++) document.write(a[i] + ", " ); document.write(a[n] + "]" ); // This code is contributed by rameshtravel07. </script> |
[1, 4, 1, 8, 1]
Time Complexity: O(N)
Auxiliary Space: O(N)