Sum of minimum elements of all subarrays
Given an array A of n integers. The task is to find the sum of minimum of all possible (contiguous) subarray of A.
Examples:
Input: A = [3, 1, 2, 4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3, 1], [1, 2], [2, 4], [3, 1, 2], [1, 2, 4], [3, 1, 2, 4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.Input : A = [1, 2, 3, 4]
Output: 20
Approach: The Naive approach is to generate all possible (contiguous) subarrays, find their minimum and add them to result.
Algorithm:
- Initialize a variable ans with value 0.
- Run two loops to find all subarrays.
- For each subarray find its minimum element and add that to ans variable.
- Print or return ans variable.
Below is the implementation of above approach:
C++
// CPP implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to return required minimum sum int sumSubarrayMins( int A[], int n) { // To store answer int ans = 0; for ( int i = 0; i < n; i++) { // To store minimum element int min_ele = A[i]; for ( int j = i; j < n; j++) { // Finding minimum element of subarray min_ele = min(min_ele, A[j]); // Adding that minimum element of subarray in // answer ans += min_ele; } } return ans; } // Driver program int main() { int A[] = { 3, 1, 2, 4 }; int n = sizeof (A) / sizeof (A[0]); // function call to get required result cout << sumSubarrayMins(A, n); return 0; } |
Java
//Java program to return required minimum sum public class GFG { // Function to return required minimum sum public static int sumSubarrayMins( int [] A) { // To store answer int ans = 0 ; int n = A.length; // Outer loop: iterate through all elements of the array for ( int i = 0 ; i < n; i++) { // To store the minimum element for the current subarray int min_ele = A[i]; // Inner loop: iterate from the current index 'i' to the end of the array for ( int j = i; j < n; j++) { // Finding the minimum element of the subarray min_ele = Math.min(min_ele, A[j]); // Adding the minimum element of the subarray to the answer ans += min_ele; } } // Return the final minimum sum of all subarrays return ans; } //Driver Code public static void main(String[] args) { int [] A = { 3 , 1 , 2 , 4 }; // Function call System.out.println(sumSubarrayMins(A)); } } |
Python3
#Python program to return required minimum sum def sumSubarrayMins(A): # To store answer ans = 0 n = len (A) for i in range (n): # To store minimum element min_ele = A[i] for j in range (i, n): # Finding minimum element of subarray min_ele = min (min_ele, A[j]) # Adding that minimum element of subarray to answer ans + = min_ele return ans # Driver code A = [ 3 , 1 , 2 , 4 ] # Function call print (sumSubarrayMins(A)) |
C#
using System; public class MainClass { // Function to return required minimum sum static int SumSubarrayMins( int [] A, int n) { // To store answer int ans = 0; for ( int i = 0; i < n; i++) { // To store minimum element int minEle = A[i]; for ( int j = i; j < n; j++) { // Finding minimum element of subarray minEle = Math.Min(minEle, A[j]); // Adding that minimum element of subarray // in answer ans += minEle; } } return ans; } public static void Main( string [] args) { int [] A = { 3, 1, 2, 4 }; int n = A.Length; // Function call to get required result Console.WriteLine(SumSubarrayMins(A, n)); } } |
Javascript
// Function to return the required minimum sum function sumSubarrayMins(A) { // To store the answer let ans = 0; const n = A.length; for (let i = 0; i < n; i++) { // To store the minimum element let min_ele = A[i]; for (let j = i; j < n; j++) { // Finding the minimum element of the subarray min_ele = Math.min(min_ele, A[j]); // Adding that minimum element of the subarray to the answer ans += min_ele; } } return ans; } // Driver program function main() { const A = [3, 1, 2, 4]; // Function call to get the required result console.log(sumSubarrayMins(A)); } main(); // This code is contributed by shivamgupta310570 |
Output-
17
Complexity Analysis:
- Time Complexity: O(N2),because of two nested for loops
- Space Complexity: O(1).
Efficient Approach: The general intuition for solution to the problem is to find sum(A[i] * f(i)), where f(i) is the number of subarrays in which A[i] is the minimum.
In order to find f[i], we need to find out:
left[i], the length of strictly larger numbers on the left of A[i],
right[i], the length of larger numbers on the right of A[i].
We make two arrays left[ ] and right[ ] such that:
left[i] + 1 equals to the number of subarrays ending with A[i], and A[i] is only single minimum.
Similarly, right[i] + 1 equals to the number of subarrays starting with A[i], and A[i] is first minimum.
Finally, f(i) = (left[i]) * (right[i]), where f[i] equals total number of subarrays in which A[i] is minimum.x
Below is the implementation of above approach
C++
// CPP implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to return required minimum sum int sumSubarrayMins( int A[], int n) { int left[n], right[n]; stack<pair< int , int > > s1, s2; // getting number of element strictly larger // than A[i] on Left. for ( int i = 0; i < n; ++i) { int cnt = 1; // get elements from stack until element // greater than A[i] found while (!s1.empty() && (s1.top().first) > A[i]) { cnt += s1.top().second; s1.pop(); } s1.push({ A[i], cnt }); left[i] = cnt; } // getting number of element larger than A[i] on Right. for ( int i = n - 1; i >= 0; --i) { int cnt = 1; // get elements from stack until element greater // or equal to A[i] found while (!s2.empty() && (s2.top().first) >= A[i]) { cnt += s2.top().second; s2.pop(); } s2.push({ A[i], cnt }); right[i] = cnt; } int result = 0; // calculating required resultult for ( int i = 0; i < n; ++i) result = (result + A[i] * left[i] * right[i]); return result; } // Driver program int main() { int A[] = { 3, 1, 2, 4 }; int n = sizeof (A) / sizeof (A[0]); // function call to get required resultult cout << sumSubarrayMins(A, n); return 0; } // This code is written by Sanjit_Prasad |
Java
// Java implementation of above approach import java.util.*; class GFG { static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to return required minimum sum static int sumSubarrayMins( int A[], int n) { int []left = new int [n]; int []right = new int [n]; Stack<pair> s1 = new Stack<pair>(); Stack<pair> s2 = new Stack<pair>(); // getting number of element strictly larger // than A[i] on Left. for ( int i = 0 ; i < n; ++i) { int cnt = 1 ; // get elements from stack until element // greater than A[i] found while (!s1.isEmpty() && (s1.peek().first) > A[i]) { cnt += s1.peek().second; s1.pop(); } s1.push( new pair(A[i], cnt)); left[i] = cnt; } // getting number of element larger // than A[i] on Right. for ( int i = n - 1 ; i >= 0 ; --i) { int cnt = 1 ; // get elements from stack until element // greater or equal to A[i] found while (!s2.isEmpty() && (s2.peek().first) >= A[i]) { cnt += s2.peek().second; s2.pop(); } s2.push( new pair(A[i], cnt)); right[i] = cnt; } int result = 0 ; // calculating required resultult for ( int i = 0 ; i < n; ++i) result = (result + A[i] * left[i] * right[i]); return result; } // Driver Code public static void main(String[] args) { int A[] = { 3 , 1 , 2 , 4 }; int n = A.length; // function call to get required result System.out.println(sumSubarrayMins(A, n)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of above approach # Function to return required minimum sum def sumSubarrayMins(A, n): left, right = [ None ] * n, [ None ] * n # Use list as stack s1, s2 = [], [] # getting number of element strictly # larger than A[i] on Left. for i in range ( 0 , n): cnt = 1 # get elements from stack until # element greater than A[i] found while len (s1) > 0 and s1[ - 1 ][ 0 ] > A[i]: cnt + = s1[ - 1 ][ 1 ] s1.pop() s1.append([A[i], cnt]) left[i] = cnt # getting number of element # larger than A[i] on Right. for i in range (n - 1 , - 1 , - 1 ): cnt = 1 # get elements from stack until # element greater or equal to A[i] found while len (s2) > 0 and s2[ - 1 ][ 0 ] > = A[i]: cnt + = s2[ - 1 ][ 1 ] s2.pop() s2.append([A[i], cnt]) right[i] = cnt result = 0 # calculating required resultult for i in range ( 0 , n): result + = A[i] * left[i] * right[i] return result # Driver Code if __name__ = = "__main__" : A = [ 3 , 1 , 2 , 4 ] n = len (A) # function call to get # required resultult print (sumSubarrayMins(A, n)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of above approach using 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 return required minimum sum static int sumSubarrayMins( int []A, int n) { int []left = new int [n]; int []right = new int [n]; Stack<pair> s1 = new Stack<pair>(); Stack<pair> s2 = new Stack<pair>(); // getting number of element strictly larger // than A[i] on Left. for ( int i = 0; i < n; ++i) { int cnt = 1; // get elements from stack until element // greater than A[i] found while (s1.Count!=0 && (s1.Peek().first) > A[i]) { cnt += s1.Peek().second; s1.Pop(); } s1.Push( new pair(A[i], cnt)); left[i] = cnt; } // getting number of element larger // than A[i] on Right. for ( int i = n - 1; i >= 0; --i) { int cnt = 1; // get elements from stack until element // greater or equal to A[i] found while (s2.Count != 0 && (s2.Peek().first) >= A[i]) { cnt += s2.Peek().second; s2.Pop(); } s2.Push( new pair(A[i], cnt)); right[i] = cnt; } int result = 0; // calculating required resultult for ( int i = 0; i < n; ++i) result = (result + A[i] * left[i] * right[i]); return result; } // Driver Code public static void Main(String[] args) { int []A = { 3, 1, 2, 4 }; int n = A.Length; // function call to get required result Console.WriteLine(sumSubarrayMins(A, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of above approach // Function to return required minimum sum function sumSubarrayMins(A, n) { var left = Array(n), right = Array(n); var s1 = [], s2 = []; // getting number of element strictly larger // than A[i] on Left. for ( var i = 0; i < n; ++i) { var cnt = 1; // get elements from stack until element // greater than A[i] found while (s1.length!=0 && (s1[s1.length-1][0]) > A[i]) { cnt += s1[s1.length-1][1]; s1.pop(); } s1.push([A[i], cnt]); left[i] = cnt; } // getting number of element larger than A[i] on Right. for ( var i = n - 1; i >= 0; --i) { var cnt = 1; // get elements from stack until element greater // or equal to A[i] found while (s2.length!=0 && (s2[s2.length-1][0]) >= A[i]) { cnt += s2[s2.length-1][1]; s2.pop(); } s2.push([A[i], cnt]); right[i] = cnt; } var result = 0; // calculating required resultult for ( var i = 0; i < n; ++i) result = (result + A[i] * left[i] * right[i]); return result; } // Driver program var A = [3, 1, 2, 4]; var n = A.length; // function call to get required resultult document.write( sumSubarrayMins(A, n)); </script> |
17
Complexity Analysis:
- Time Complexity: O(N), where N is the length of A.
- Space Complexity: O(N).
Another Approach:
It is a dynamic programming approach.
First, calculate the next smaller element index on the right side for each index using stacks.
At any index i, dp[i] denotes the total sum of all the sub-arrays starting from index i.
For calculating the answer for each index, there will be two cases :
- The current element is the smallest element amongst all the elements on the right-hand side. So ans will be (( range of curr_index * arr[curr_index] )) . As it will be the smallest element in all the sub-arrays starting from curr_index.
- There is an element present on right, which is smaller than the current element. Answer from that smaller_element is already stored in dp. Just Calculate the answer from current_index to smaller_right_index.
- upto_smaller = (right_index – curr_index)*arr[curr_index] ## sum up to right smaller index form curr_index .
- curr_sum = upto_smaller + dp[right_index]
Finally , return the sum(dp).
For eg :- arr = [4,3,6]
dp[6] = 6
dp[3] => (3-1)*3 => 6 #smallest element
dp[4] = (1 -0) *(4) + dp[3] => 4 + 6 => 10
Final answer = 6 + 6 + 10= 22
Implementation:
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; int sumSubarrayMins( int arr[], int n) { int dp[n]; for ( int i = 0; i < n; i++) dp[i] = 0; // calculate right smaller element int right[n]; for ( int i = 0; i < n; i++) { right[i] = i; } vector< int > stack{ 0 }; for ( int i = 1; i < n; i++) { int curr = arr[i]; while ((stack.size() > 0) && (curr < arr[stack.back()])) { int idx = stack.back(); stack.pop_back(); right[idx] = i; } stack.push_back(i); } dp[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { int right_idx = right[i]; if (right_idx == i) { // case 1 int curr = (n - i) * arr[i]; dp[i] = curr; } else { // case 2 // sum upto next smaller rhs element int upto_small = (right_idx - i) * (arr[i]); int curr_sum = (upto_small + dp[right_idx]); dp[i] = curr_sum; } } //calculating sum of dp int sum = 0; sum = accumulate(dp, dp + n, sum); return sum; } // Driver Code int main() { int A[] = { 3, 1, 2, 4 }; int n = sizeof (A) / sizeof (A[0]); // function call to get // required result cout << sumSubarrayMins(A, n) << endl; } // This code is contributed by phasing17 |
Java
// Java program to implement the approach import java.util.*; public class GFG { static int sumSubarrayMins( int [] arr, int n) { int dp[] = new int [n]; for ( int i = 0 ; i < n; i++) dp[i] = 0 ; // calculate right smaller element int right[] = new int [n]; for ( int i = 0 ; i < n; i++) { right[i] = i; } ArrayList<Integer> stack = new ArrayList<Integer>(); stack.add( 0 ); for ( int i = 1 ; i < n; i++) { int curr = arr[i]; while ( (stack.size() > 0 ) && (curr < arr[stack.get(stack.size() - 1 )])) { int idx = stack.get(stack.size() - 1 ); stack.remove(stack.size() - 1 ); right[idx] = i; } stack.add(i); } dp[n - 1 ] = arr[n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i--) { int right_idx = right[i]; if (right_idx == i) { // case 1 int curr = (n - i) * arr[i]; dp[i] = curr; } else { // case 2 // sum upto next smaller rhs element int upto_small = (right_idx - i) * (arr[i]); int curr_sum = (upto_small + dp[right_idx]); dp[i] = curr_sum; } } // calculating sum of dp int sum = 0 ; for ( int i = 0 ; i < dp.length; i++) sum += dp[i]; return sum; } // Driver Code public static void main(String[] args) { int A[] = { 3 , 1 , 2 , 4 }; int n = A.length; // function call to get // required result System.out.println(sumSubarrayMins(A, n)); } } // This code is contributed by phasing17 |
Python3
def sumSubarrayMins(arr, n): dp = [ 0 ] * (n) # calculate right smaller element right = [i for i in range (n)] stack = [ 0 ] for i in range ( 1 ,n, 1 ): curr = arr[i] while (stack and curr < arr[stack[ - 1 ]]): idx = stack.pop() right[idx] = i stack.append(i) dp[ - 1 ] = arr[ - 1 ] for i in range (n - 2 , - 1 , - 1 ): right_idx = right[i] if right_idx = = i: # case 1 curr = (n - i) * arr[i] dp[i] = curr else : # case 2 # sum upto next smaller rhs element upto_small = (right_idx - i) * (arr[i]) curr_sum = (upto_small + dp[right_idx]) dp[i] = curr_sum return ( sum (dp)) # Driver Code if __name__ = = "__main__" : A = [ 3 , 1 , 2 , 4 ] n = len (A) # function call to get # required resultult print (sumSubarrayMins(A, n)) |
C#
// Include namespace system using System; using System.Collections.Generic; public class GFG { public static int sumSubarrayMins( int [] arr, int n) { int [] dp = new int [n]; for ( int i = 0; i < n; i++) { dp[i] = 0; } // calculate right smaller element int [] right = new int [n]; for ( int i = 0; i < n; i++) { right[i] = i; } var stack = new List< int >(); stack.Add(0); for ( int i = 1; i < n; i++) { var curr = arr[i]; while ((stack.Count > 0) && (curr < arr[stack[stack.Count - 1]])) { var idx = stack[stack.Count - 1]; stack.RemoveAt(stack.Count - 1); right[idx] = i; } stack.Add(i); } dp[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { var right_idx = right[i]; if (right_idx == i) { // case 1 var curr = (n - i) * arr[i]; dp[i] = curr; } else { // case 2 // sum upto next smaller rhs element var upto_small = (right_idx - i) * (arr[i]); var curr_sum = (upto_small + dp[right_idx]); dp[i] = curr_sum; } } // calculating sum of dp var sum = 0; for ( int i = 0; i < dp.Length; i++) { sum += dp[i]; } return sum; } // Driver Code public static void Main(String[] args) { int [] A = {3, 1, 2, 4}; var n = A.Length; // function call to get // required result Console.WriteLine(GFG.sumSubarrayMins(A, n)); } } // This code is contributed by utkarshshirode02 |
Javascript
<script> function sumSubarrayMins(arr, n) { let dp = new Array(n).fill(0) // calculate right smaller element let right = new Array(n); for (let i = 0; i < n; i++) { right[i] = i; } let stack = [0] for (let i = 1; i < n; i++){ let curr = arr[i] while (stack && curr < arr[stack[stack.length-1]]){ let idx = stack.shift() right[idx] = i } stack.push(i) } dp[dp.length - 1] = arr[arr.length - 1] for (let i = n - 2; i >= 0; i--){ let right_idx = right[i] if (right_idx == i){ // case 1 let curr = (n - i)*arr[i] dp[i] = curr } else { // case 2 // sum upto next smaller rhs element let upto_small = (right_idx-i)*(arr[i]) let curr_sum = (upto_small + dp[right_idx]) dp[i] = curr_sum } } let sum = 0 for (let i of dp){ sum += i } return sum } // Driver Code let A = [3, 1, 2, 4] let n = A.length // function call to get // required resultult document.write(sumSubarrayMins(A, n)) // This code is contributed by shinjanpatra </script> |
17
Complexity Analysis:
- Time Complexity: O(N)
- Space Complexity: O(N)