Sum of Subarray Minimums
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.
Input
weights: an array of integers
Output
the sum of subarray minimums
Examples
Example 1:
Input:
1weights = [1, 3, 2]
Output: 10
Explanation:
| Subarray | Min Weight |
|---|---|
| 1 ,3, 2 | 1 |
| 1, 3, 2 | 3 |
| 1, 3, 2 | 2 |
| 1, 3, 2 | 1 |
| 1, 3, 2 | 2 |
| 1, 3, 2 | 1 |
The the sum of subarray minimums is 1+3+2+1+2+1=10.
Try it yourself
Solution
Brute Force
The brute force solution to this problem would to do exactly what we're told in the question. That is, find the minimum of each subarray and calculate the sum of these values. Here's a visual representation of this idea:
And here's the code for this idea:
1int sum_subarray(vector<int> weights) {
2 int sum = 0;
3 int n = (int) weights.size();
4
5 for (int start = 0; start < n; start++) {
6 int min_of_subarray = weights[start];
7 for (int end = start; end < n; end++) {
8 min_of_subarray = min(min_of_subarray, weights[end]);
9 sum += min_of_subarray;
10 }
11 }
12
13 return sum;
14}
151public static int sumSubarray(List<Integer> weights) {
2 int sum = 0;
3 int n = weights.size();
4
5 for (int start = 0; start < n; start++) {
6 int minOfSubarray = weights.get(start);
7 for (int end = start; end < n; end++) {
8 minOfSubarray = Math.min(minOfSubarray, weights.get(end));
9 sum += minOfSubarray;
10 }
11 }
12
13 return sum;
14}
151function sumSubarray(weights) {
2 let sum = 0;
3 const n = weights.length;
4
5 for (let start = 0; start < n; start++) {
6 let minOfSubarray = weights[start];
7 for (let end = start; end < n; end++) {
8 minOfSubarray = Math.min(minOfSubarray, weights[end]);
9 sum += minOfSubarray;
10 }
11 }
12
13 return sum;
14}
151def sum_subarray(weights: List[int]) -> int:
2 sum = 0
3 n = len(weights)
4
5 for start in range(n):
6 min_of_subarray = weights[start]
7 for end in range(start, n):
8 min_of_subarray = min(min_of_subarray, weights[end])
9 sum += min_of_subarray
10
11 return sum
12The time complexity of this solution would be O(n^2) where n is the number of elements in weights since it takes
O(n^2) to generate all subarray and we can find the minimum of each one as we generate them. The space complexity is
O(1) since we do not use any additional memory.
Monotonic Stack
How can we improve our solution to O(n)?
This problem can be solved using Monotonic Stack in O(n). The idea is similar to Sliding Window Maximum.
Since we need to consider all [i, j] subarrays for 0<=i<=j<=len(arr)-1, we can iterate j. For each iteration, we fix j and consider j+1 subarrays for 0<=i<=j. The idea is to maintain a monotonic stack of (value, count) pair of the minimums of j+1 subarrays.
For example, suppose the array is [1,3,2].
- For
j=0, the only subarray is[1], sostack = [(1,1)]. - For
j=1, the subarrays are[1,3]and[3], sostack = [(1,1), (3,1)]. - For
j=2, the subarrays are[1,3,2],[3,2], and[2], sostack = [(1,1), (2,2)].
But how should we maintain the stack? Notice that min(arr[i,j+1])=min(arr[i,j],arr[j+1]). The idea is to pop the stack until the value at the top is less than the current arr[j]. Suppose we poped a pair (value, count), it means that there are count [i,j-1] subarrays with minimum value. Since our current value arr[j] is less or equal than value, for those [i, j] subarrays, the minimum changed from value to curValue(arr[j]), so we add count to curCount. At the end, we push (curValue, curCount) to the stack.
And how should we use the stack to calculate the sum of minimums? Clearly, we can sum over the stack for each iteration of j, but that would be O(n) for each iteration and O(n^2) in total. The idea is to maintain a curSum, which is the sum of subarray minimums for fixed j, as we maintain the stack. When we pop (value, count), we subtract value*count from curSum, as the minimum of those subarrays changed from value to curValue, and we add curValue*curCount after popping the stack.
1from typing import List
2
3def sum_subarray(weights: List[int]) -> int:
4 stack = []
5 sum = 0
6 curSum = 0
7 for curValue in weights:
8 curCount = 1
9 while stack:
10 if stack[-1][0] < curValue:
11 break
12 value, count = stack.pop()
13 curCount += count
14 curSum -= value * count
15
16 stack.append((curValue, curCount))
17 curSum += curValue * curCount
18 sum += curSum
19 return sum
20
21if __name__ == '__main__':
22 weights = [int(x) for x in input().split()]
23 res = sum_subarray(weights)
24 print(res)
251import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.Stack;
5import java.util.stream.Collectors;
6
7class Solution {
8 public static int sumSubarray(List<Integer> arr) {
9 int sum = 0;
10 Stack<Integer> valueStack = new Stack<Integer>();
11 Stack<Integer> countStack = new Stack<Integer>();
12 int curSum = 0;
13 for (int curValue : arr) {
14 int curCount = 1;
15 while (!valueStack.empty()) {
16 if (valueStack.peek() < curValue) {
17 break;
18 }
19 int value = valueStack.pop();
20 int count = countStack.pop();
21 curCount += count;
22 curSum -= value * count;
23 }
24 valueStack.push(curValue);
25 countStack.push(curCount);
26 curSum += curValue * curCount;
27 sum += curSum;
28 }
29 return sum;
30 }
31
32 public static List<String> splitWords(String s) {
33 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
34 }
35
36 public static void main(String[] args) {
37 Scanner scanner = new Scanner(System.in);
38 List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
39 scanner.close();
40 int res = sumSubarray(weights);
41 System.out.println(res);
42 }
43}
441function sumSubarray(weights) {
2 const stack = [];
3 let sum = 0, curSum = 0;
4 for (let weight of weights) {
5 let curCount = 1;
6 while (stack.length > 0) {
7 if (stack[stack.length - 1][0] < weight) break;
8 let [value, count] = stack.pop();
9 curCount += count;
10 curSum -= value * count;
11 }
12 stack.push([weight, curCount]);
13 curSum += weight * curCount;
14 sum += curSum;
15 }
16 return sum;
17}
18
19function splitWords(s) {
20 return s == "" ? [] : s.split(' ');
21}
22
23function* main() {
24 const weights = splitWords(yield).map((v) => parseInt(v));
25 const res = sumSubarray(weights);
26 console.log(res);
27}
28
29class EOFError extends Error {}
30{
31 const gen = main();
32 const next = (line) => gen.next(line).done && process.exit();
33 let buf = '';
34 next();
35 process.stdin.setEncoding('utf8');
36 process.stdin.on('data', (data) => {
37 const lines = (buf + data).split('\n');
38 buf = lines.pop();
39 lines.forEach(next);
40 });
41 process.stdin.on('end', () => {
42 buf && next(buf);
43 gen.throw(new EOFError());
44 });
45}
46Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.