> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Sum of Subarray Minimums Python Solution

> Tested Python solution for LeetCode 907 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 907, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Stack](/catalog/topics/stack), [Monotonic Stack](/catalog/topics/monotonic-stack). [View on LeetCode](https://leetcode.com/problems/sum-of-subarray-minimums/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 907   # by problem number
lcpy gen -s sum_of_subarray_minimums   # by problem name
```

## Problem

Given an array of integers \<code>arr\</code>, find the sum of \<code>min(b)\</code>, where \<code>b\</code> ranges over every (contiguous) subarray of \<code>arr\</code>. Since the answer may be large, return the answer \<strong>modulo\</strong> \<code>10\<sup>9\</sup> + 7\</code>.

### Examples

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

```
Input: arr = [50]
Output: 50
```

### Constraints

* 1 \<= arr.length \<= 3 \* 10^4
* 1 \<= arr\[i] \<= 3 \* 10^4

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sum_of_subarray_minimums/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sum_of_subarray_minimums/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(n)
    def sum_subarray_mins(self, arr: list[int]) -> int:
        mod = 1_000_000_007
        n = len(arr)
        stack: list[int] = []
        prev = [0] * n
        for i, value in enumerate(arr):
            while stack and arr[stack[-1]] >= value:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)
        stack.clear()
        next_ = [0] * n
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            next_[i] = stack[-1] if stack else n
            stack.append(i)
        return sum(value * (i - prev[i]) * (next_[i] - i) for i, value in enumerate(arr)) % mod
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.