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

# 907. Sum of Subarray Minimums

## Problem Statement

<br>

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`.

&#x20;

**Example 1:**

<pre><code><strong>Input: arr = [3,1,2,4]
</strong><strong>Output: 17
</strong><strong>Explanation: 
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: arr = [11,81,94,43,3]
</strong><strong>Output: 444
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:
Brute:
In N^2 generate all sub-arrays , Then Take one more N to find min in arrays
N^3

Optimal
Use stack

Basically find the ith element is min till what range in left and right
Let
arr = 3 1 2 4
lef = 1 2 1 1 
rig = 1 3 2 1

Now, arr*left*right is answer  
```

### Links

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

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:

    int sumSubarrayMins(vector<int>& arr) {
        int n= arr.size();
        vector<int> left(n),right(n);
        stack<pair<int,int>>s,s2;

        for(int i=0;i<n;i++){
            int count=1;
            while(!s.empty() and s.top().first > arr[i]){
                count+=s.top().second;
                s.pop();
            }
            s.push({arr[i],count});
            left[i]=count;
        }

        for(int i=n-1;i>=0;i--){
            int count=1;
            while(!s2.empty() and s2.top().first >= arr[i]){
                count+=s2.top().second;
                s2.pop();
            }
            s2.push({arr[i],count});
            right[i]=count;
        }

        long long int sum=0,mod=1e9+7;

        for (int i = 0; i < n; i++){
            sum=(sum+(long long int)arr[i]*left[i]*right[i])%mod;
        }

        return sum;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###