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:

weights = [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:

1def sum_subarray(weights: list[int]) -> int:
2    total = 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            total += min_of_subarray
10
11    return total
12
13if __name__ == "__main__":
14    weights = [int(x) for x in input().split()]
15    res = sum_subarray(weights)
16    print(res)
17

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int sumSubarray(List<Integer> weights) {
8        int sum = 0;
9        int n = weights.size();
10
11        for (int start = 0; start < n; start++) {
12            int minOfSubarray = weights.get(start);
13            for (int end = start; end < n; end++) {
14                minOfSubarray = Math.min(minOfSubarray, weights.get(end));
15                sum += minOfSubarray;
16            }
17        }
18
19        return sum;
20    }
21
22    public static List<String> splitWords(String s) {
23        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
24    }
25
26    public static void main(String[] args) {
27        Scanner scanner = new Scanner(System.in);
28        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
29        scanner.close();
30        int res = sumSubarray(weights);
31        System.out.println(res);
32    }
33}
34

1"use strict";
2
3function sumSubarray(weights) {
4    let sum = 0;
5    const n = weights.length;
6
7    for (let start = 0; start < n; start++) {
8        let minOfSubarray = weights[start];
9        for (let end = start; end < n; end++) {
10            minOfSubarray = Math.min(minOfSubarray, weights[end]);
11            sum += minOfSubarray;
12        }
13    }
14
15    return sum;
16}
17
18function splitWords(s) {
19    return s === "" ? [] : s.split(" ");
20}
21
22function* main() {
23    const weights = splitWords(yield).map((v) => parseInt(v));
24    const res = sumSubarray(weights);
25    console.log(res);
26}
27
28class EOFError extends Error {}
29{
30    const gen = main();
31    const next = (line) => gen.next(line).done && process.exit();
32    let buf = "";
33    next();
34    process.stdin.setEncoding("utf8");
35    process.stdin.on("data", (data) => {
36        const lines = (buf + data).split("\n");
37        buf = lines.pop();
38        lines.forEach(next);
39    });
40    process.stdin.on("end", () => {
41        buf && next(buf);
42        gen.throw(new EOFError());
43    });
44}
45

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int sum_subarray(std::vector<int>& weights) {
9    int sum = 0;
10    int n = weights.size();
11
12    for (int start = 0; start < n; start++) {
13        int min_of_subarray = weights[start];
14        for (int end = start; end < n; end++) {
15            min_of_subarray = std::min(min_of_subarray, weights[end]);
16            sum += min_of_subarray;
17        }
18    }
19
20    return sum;
21}
22
23template<typename T>
24std::vector<T> get_words() {
25    std::string line;
26    std::getline(std::cin, line);
27    std::istringstream ss{line};
28    ss >> std::boolalpha;
29    std::vector<T> v;
30    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
31    return v;
32}
33
34int main() {
35    std::vector<int> weights = get_words<int>();
36    int res = sum_subarray(weights);
37    std::cout << res << '\n';
38}
39

The 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], so stack = [(1,1)].
For j=1, the subarrays are [1,3] and [3], so stack = [(1,1), (3,1)].
For j=2, the subarrays are [1,3,2], [3,2], and [2], so stack = [(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.

1def sum_subarray(weights: list[int]) -> int:
2    stack: list[tuple[int, int]] = []
3    total = 0
4    cur_sum = 0
5    for cur_value in weights:
6        cur_count = 1
7        while stack:
8            if stack[-1][0] < cur_value:
9                break
10            value, count = stack.pop()
11            cur_count += count
12            cur_sum -= value * count
13
14        stack.append((cur_value, cur_count))
15        cur_sum += cur_value * cur_count
16        total += cur_sum
17    return total
18
19if __name__ == "__main__":
20    weights = [int(x) for x in input().split()]
21    res = sum_subarray(weights)
22    print(res)
23

1import 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}
44

1"use strict";
2
3function sumSubarray(weights) {
4    const stack = [];
5    let sum = 0;
6    let curSum = 0;
7    for (const weight of weights) {
8        let curCount = 1;
9        while (stack.length > 0) {
10            if (stack[stack.length - 1][0] < weight) break;
11            const [value, count] = stack.pop();
12            curCount += count;
13            curSum -= value * count;
14        }
15        stack.push([weight, curCount]);
16        curSum += weight * curCount;
17        sum += curSum;
18    }
19    return sum;
20}
21
22function splitWords(s) {
23    return s === "" ? [] : s.split(" ");
24}
25
26function* main() {
27    const weights = splitWords(yield).map((v) => parseInt(v));
28    const res = sumSubarray(weights);
29    console.log(res);
30}
31
32class EOFError extends Error {}
33{
34    const gen = main();
35    const next = (line) => gen.next(line).done && process.exit();
36    let buf = "";
37    next();
38    process.stdin.setEncoding("utf8");
39    process.stdin.on("data", (data) => {
40        const lines = (buf + data).split("\n");
41        buf = lines.pop();
42        lines.forEach(next);
43    });
44    process.stdin.on("end", () => {
45        buf && next(buf);
46        gen.throw(new EOFError());
47    });
48}
49