> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0907-sum-of-subarray-minimums.md).

# 0907. Sum of Subarray Minimums

<https://leetcode.com/problems/sum-of-subarray-minimums>

## Description

Given an array of integers arr, find the sum of `min(b)`, where `b` ranges over every (contiguous) subarray of `arr`. Since the answer may be large, return the answer **modulo** `109 + 7`.

**Example 1:**

```
**Input:** arr = [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.
```

**Example 2:**

```
**Input:** arr = [11,81,94,43,3]
**Output:** 444
```

**Constraints:**

* `1 <= arr.length <= 3 * 104`
* `1 <= arr[i] <= 3 * 104`

## ac: Monotoic queue

```java
class Solution {
    public int sumSubarrayMins(int[] arr) {
        int[] PLE = new int[arr.length]; // Number of previous larger element
        int[] NLE = new int[arr.length]; // Number of next larger element
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int largerIndex = stack.pop();
                NLE[largerIndex] = i - largerIndex - 1;
            }
            PLE[i] = stack.isEmpty() ? i : i - stack.peek() - 1;
            stack.push(i);
        }
        
        // There are remaining elements in stack, e.g. [1,2,3,4,5]
        while (!stack.isEmpty()) {
            int index = stack.pop();
            NLE[index] = arr.length - index - 1;
        }
        
        long sum = 0;
        long MOD = (long) 1e9 + 7;
        for (int i = 0; i < arr.length; i++) {
            // See below explanation to calculate number of subarray.
            long subarrayCount = (PLE[i] + 1) * (NLE[i] + 1);
            sum = (sum + subarrayCount * arr[i]) % MOD;
        }
        
        return (int) sum;
    }
}

/*
O(N) time, O(N) space.

The number of subarrays with 3 in it will be anything that starts in [L..3] and ends in [3..R]. So we have [L..3] starting positions and [3..R] ending positions. 
In other words, we have d1 starting positions and d2 ending positions. So the total number of subarrays is just d1*d2.

For example:
in [9,7,8,3,4,6]
we have 4 choices to start with (9,7,8,3)
we have 3 choices to end with (3,4,6)

So answer is just 4*3.
*/
```