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}
Hashing Approach: Traverse the array to find the minimum element for all possible subarrays and store their count in a Map. Follow the steps below to solve the problem:
- Create a Map to store the count of subarrays for each element.
- Traverse over all the possible subarray find the minimum element in the subarray.
- Increment count of the minimum elements obtained in the Map.
- Finally, print the frequencies obtained in the Map for each array element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate total number// of sub-arrays for each element// where that element is occurring// as the minimum elementvoid minSubarray(int* arr, int N){ // Map for storing the number of // sub-arrays for each element unordered_map<int, int> m; // Traverse over all possible subarrays for (int i = 0; i < N; i++) { int mini = INT_MAX; for (int j = i; j < N; j++) { // Minimum in each subarray mini = min(mini, arr[j]); m[mini]++; } } // Print the result for (int i = 0; i < N; i++) { cout << m[arr[i]] << " "; }}// Driver Codeint main(){ int arr[] = { 3, 2, 1, 4 }; int N = sizeof(arr) / sizeof(int); // Function Call minSubarray(arr, N); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Function to calculate total // number of sub-arrays for each // element where that element is // occurring as the minimum elementstatic void minSubarray(int []arr, int N){ // Map for storing the number of // sub-arrays for each element HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse over all possible // subarrays for (int i = 0; i < N; i++) { int mini = Integer.MAX_VALUE; for (int j = i; j < N; j++) { // Minimum in each subarray mini = Math.min(mini, arr[j]); if(mp.containsKey(mini)) { mp.put(mini, mp.get(mini) + 1); } else { mp.put(mini, 1); } } } // Print the result for (int i = 0; i < N; i++) { System.out.print(mp.get(arr[i]) + " "); }}// Driver Codepublic static void main(String[] args){ int arr[] = {3, 2, 1, 4}; int N = arr.length; // Function Call minSubarray(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for # the above approach# Function to calculate total # number of sub-arrays for # each element where that # element is occurring as the # minimum elementdef minSubarray(arr, N): # Map for storing the # number of sub-arrays # for each element m = {} # Traverse over all # possible subarrays for i in range(N): mini = 10 ** 9 for j in range(i, N): # Minimum in each subarray mini = min(mini, arr[j]) m[mini] = m.get(mini, 0) + 1 # Print result for i in arr: print(m[i], end = " ")# Driver Codeif __name__ == '__main__': arr = [3, 2, 1, 4] N = len(arr) # Function Call minSubarray(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate total // number of sub-arrays for each // element where that element is // occurring as the minimum elementstatic void minSubarray(int []arr, int N){ // Map for storing the number of // sub-arrays for each element Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse over all possible // subarrays for(int i = 0; i < N; i++) { int mini = int.MaxValue; for(int j = i; j < N; j++) { // Minimum in each subarray mini = Math.Min(mini, arr[j]); if (mp.ContainsKey(mini)) { mp[mini] = mp[mini] + 1; } else { mp.Add(mini, 1); } } } // Print the result for(int i = 0; i < N; i++) { Console.Write(mp[arr[i]] + " "); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 3, 2, 1, 4 }; int N = arr.Length; // Function Call minSubarray(arr, N);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to calculate total number// of sub-arrays for each element// where that element is occurring// as the minimum elementfunction minSubarray(arr, N){ // Map for storing the number of // sub-arrays for each element var m = new Map(); // Traverse over all possible subarrays for (var i = 0; i < N; i++) { var mini = 1000000000; for (var j = i; j < N; j++) { // Minimum in each subarray mini = Math.min(mini, arr[j]); if(m.has(mini)) m.set(mini, m.get(mini)+1) else m.set(mini, 1) } } // Print the result for (var i = 0; i < N; i++) { document.write( m.get(arr[i]) + " "); }}// Driver Codevar arr = [3, 2, 1, 4];var N = arr.length;// Function CallminSubarray(arr, N);</script> |
Output
1 2 6 1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: This approach is based on the concept of the next greater element and previous greater element. Follow the steps below to solve the problem:
- In order to find the occurrence of the element as a minimum, first find x and y, where x is the length of strictly larger numbers on the left of arr[i] and y is the length of larger numbers on the right of arr[i].
- Thus, x * y is the total number of subarrays in which arr[i] is a minimum.
- To find x and y use stack with the concept of the next greater element and previous greater element.
- For the next greater element, create a stack of pairs and push the first array element and a counter to count the subarrays as a pair into the stack.
- Traverse the array and pick the array element one by one:
- If the current array element is greater than the top element of the stack, then for the top element in the Stack, the current element is the next greater element. So, pop out the top element of the stack and increment the counter by the counter value on the top of the stack, and then the next top stack element is compared with the current array element and so on.
- Otherwise, push the current array element with the counter into the stack and insert the counter into the result array.
- Repeat steps 4, 5 for the previous greater element.
- Finally, print the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count subarrays// for each element where it is// the minimumvoid minSubarray(int* arr, int N){ int result[N]; stack<pair<int, int> > l, r; // For the length of strictly larger // numbers on the left of A[i] for (int i = 0; i < N; i++) { int count = 1; while (!l.empty() && l.top().first > arr[i]) { count += l.top().second; l.pop(); } l.push({ arr[i], count }); // Storing x in result[i] result[i] = count; } // For the length of strictly larger // numbers on the right of A[i] for (int i = N - 1; i >= 0; i--) { int count = 1; while (!r.empty() && r.top().first >= arr[i]) { count += r.top().second; r.pop(); } r.push({ arr[i], count }); // Store x*y in result array result[i] *= count; } // Print the result for (int i = 0; i < N; i++) { cout << result[i] << " "; }}// Driver Codeint main(){ int arr[] = { 3, 2, 1, 4 }; int N = sizeof(arr) / sizeof(int); // Function Call minSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to count subarrays// for each element where it is// the minimumstatic void minSubarray(int []arr, int N){ int []result = new int[N]; Stack<pair> l = new Stack<>(); Stack<pair> r = new Stack<>(); // For the length of strictly larger // numbers on the left of A[i] for(int i = 0; i < N; i++) { int count = 1; while (!l.isEmpty() && l.peek().first > arr[i]) { count += l.peek().second; l.pop(); } l.add(new pair(arr[i], count)); // Storing x in result[i] result[i] = count; } // For the length of strictly larger // numbers on the right of A[i] for(int i = N - 1; i >= 0; i--) { int count = 1; while (!r.isEmpty() && r.peek().first >= arr[i]) { count += r.peek().second; r.pop(); } r.add(new pair(arr[i], count)); // Store x*y in result array result[i] *= count; } // Print the result for(int i = 0; i < N; i++) { System.out.print(result[i] + " "); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 2, 1, 4 }; int N = arr.length; // Function Call minSubarray(arr, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the # above approach# Function to count subarrays# for each element where it is# the minimumdef minSubarray(arr, N): result = [0] * N l = [] r = [] # For the length of strictly # larger numbers on the left # of A[i] for i in range(N): count = 1; while (len(l) != 0 and l[-1][0] > arr[i]): count += l[-1][1] l.pop() l.append([arr[i], count]) # Storing x in result[i] result[i] = count; # For the length of # strictly larger # numbers on the # right of A[i] for i in range(N - 1, -1, -1): count = 1; while (len(r) != 0 and r[-1][0] >= arr[i]): count += r[-1][1] r.pop(); r.append([arr[i], count]); # Store x*y in result # array result[i] *= count # Print the result for i in range(N): print(result[i], end = " ")# Driver Codeif __name__ == "__main__": arr = [3, 2, 1, 4] N = len(arr) # Function Call minSubarray(arr, N)# This code is contributed by Chitranayal |
C#
// C# program for the// above approachusing System;using System.Collections.Generic;class GFG{public class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to count subarrays// for each element where it is// the minimumstatic void minSubarray(int []arr, int N){ int []result = new int[N]; Stack<pair> l = new Stack<pair>(); Stack<pair> r = new Stack<pair>(); // For the length of strictly // larger numbers on the left // of A[i] for(int i = 0; i < N; i++) { int count = 1; while (l.Count != 0 && l.Peek().first > arr[i]) { count += l.Peek().second; l.Pop(); } l.Push(new pair(arr[i], count)); // Storing x in result[i] result[i] = count; } // For the length of strictly // larger numbers on the right // of A[i] for(int i = N - 1; i >= 0; i--) { int count = 1; while (r.Count != 0 && r.Peek().first >= arr[i]) { count += r.Peek().second; r.Pop(); } r.Push(new pair(arr[i], count)); // Store x*y in result array result[i] *= count; } // Print the result for(int i = 0; i < N; i++) { Console.Write(result[i] + " "); }}// Driver Codepublic static void Main(String[] args){ int []arr = {3, 2, 1, 4}; int N = arr.Length; // Function Call minSubarray(arr, N);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to count subarrays// for each element where it is// the minimumfunction minSubarray(arr,N){ let result = new Array(N); for(let i=0;i<N;i++) result[i]=0; let l = []; let r = []; // For the length of strictly larger // numbers on the left of A[i] for(let i = 0; i < N; i++) { let count = 1; while (l.length!=0 && l[l.length-1][0] > arr[i]) { count += l[l.length-1][1]; l.pop(); } l.push([arr[i], count]); // Storing x in result[i] result[i] = count; } // For the length of strictly larger // numbers on the right of A[i] for(let i = N - 1; i >= 0; i--) { let count = 1; while (r.length!=0 && r[r.length-1][0] >= arr[i]) { count += r[r.length-1][1]; r.pop(); } r.push([arr[i], count]); // Store x*y in result array result[i] *= count; } // Print the result for(let i = 0; i < N; i++) { document.write(result[i] + " "); }}// Driver Codelet arr=[3, 2, 1, 4 ];let N = arr.length;// Function CallminSubarray(arr, N);// This code is contributed by avanitrachhadiya2155</script> |
Output
1 2 6 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
