# LeetCode 907: Sum of Subarray Minimums

## Problem Restatement

We are given an integer array `arr`.

For every contiguous subarray, take the minimum value of that subarray.

Return the sum of all those minimum values.

Because the answer can be large, return it modulo:

```python
10**9 + 7
```

For example:

```python
arr = [3, 1, 2, 4]
```

All subarray minimums are:

```python
[3]          -> 3
[3, 1]       -> 1
[3, 1, 2]    -> 1
[3, 1, 2, 4] -> 1
[1]          -> 1
[1, 2]       -> 1
[1, 2, 4]    -> 1
[2]          -> 2
[2, 4]       -> 2
[4]          -> 4
```

The sum is:

```python
3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `arr` |
| Output | Sum of minimum values over all contiguous subarrays |
| Modulo | `10^9 + 7` |
| Key requirement | Count every contiguous subarray exactly once |

Function shape:

```python
def sumSubarrayMins(arr: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [3, 1, 2, 4]
```

Answer:

```python
17
```

Example 2:

```python
arr = [11, 81, 94, 43, 3]
```

Answer:

```python
444
```

## First Thought: Enumerate All Subarrays

A direct method is to generate every subarray and track the minimum.

```python
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        answer = 0

        for left in range(n):
            current_min = arr[left]

            for right in range(left, n):
                current_min = min(current_min, arr[right])
                answer += current_min

        return answer % MOD
```

This works, but it has quadratic time complexity.

If `arr` has length `n`, there are `n * (n + 1) / 2` subarrays.

For large input, this is too slow.

## Key Insight

Instead of asking:

“How do we find the minimum of every subarray?”

ask:

“How many subarrays have `arr[i]` as their minimum?”

If `arr[i]` is the minimum for `count` subarrays, then its contribution is:

```python
arr[i] * count
```

So the answer is the sum of each element's contribution.

For each index `i`, we need:

1. How far can we extend left while keeping `arr[i]` as the minimum?
2. How far can we extend right while keeping `arr[i]` as the minimum?

Then:

```python
count = left_choices * right_choices
```

## Handling Equal Values

Equal values need careful tie-breaking.

We want each subarray to be assigned to exactly one minimum index.

A common rule is:

- On the left, stop at the previous element strictly less than `arr[i]`.
- On the right, stop at the next element less than or equal to `arr[i]`.

This makes equal values belong consistently to one side and prevents double counting.

For index `i`:

```python
left[i] = index of previous value < arr[i]
right[i] = index of next value <= arr[i]
```

Then:

```python
left_choices = i - left[i]
right_choices = right[i] - i
```

Contribution:

```python
arr[i] * left_choices * right_choices
```

## Algorithm

Use monotonic stacks.

First pass, compute `left[i]`.

For each `i`, remove stack values that are greater than or equal to `arr[i]`.

After popping, the top is the previous strictly smaller element.

Second pass, compute `right[i]`.

For each `i` from right to left, remove stack values that are greater than `arr[i]`.

After popping, the top is the next smaller or equal element.

Then sum all contributions.

## Correctness

For each index `i`, `left[i]` is the nearest index to the left with value strictly less than `arr[i]`.

So any valid subarray where `arr[i]` is the selected minimum can start at any position from `left[i] + 1` through `i`.

That gives:

```python
i - left[i]
```

choices.

Similarly, `right[i]` is the nearest index to the right with value less than or equal to `arr[i]`.

So the subarray can end at any position from `i` through `right[i] - 1`.

That gives:

```python
right[i] - i
```

choices.

Every subarray counted for index `i` has no smaller value inside it. Also, the tie rule ensures that if multiple equal minimum values exist, exactly one index owns that subarray.

Thus each subarray contributes its minimum value exactly once.

Summing all contributions gives the required answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each index is pushed and popped at most once per pass |
| Space | `O(n)` | Arrays `left`, `right`, and the stack |

## Implementation

```python
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)

        left = [-1] * n
        right = [n] * n

        stack = []

        for i, value in enumerate(arr):
            while stack and arr[stack[-1]] >= value:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        stack = []

        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        answer = 0

        for i, value in enumerate(arr):
            left_choices = i - left[i]
            right_choices = right[i] - i
            answer += value * left_choices * right_choices

        return answer % MOD
```

## Code Explanation

Initialize boundaries:

```python
left = [-1] * n
right = [n] * n
```

If no smaller element exists on the left, we use `-1`.

If no smaller or equal element exists on the right, we use `n`.

The first stack pass finds the previous strictly smaller value:

```python
while stack and arr[stack[-1]] >= value:
    stack.pop()
```

After this loop, the stack top is smaller than `value`, so it becomes `left[i]`.

The second stack pass finds the next smaller or equal value:

```python
while stack and arr[stack[-1]] > arr[i]:
    stack.pop()
```

After this loop, the stack top has value less than or equal to `arr[i]`, so it becomes `right[i]`.

Finally, compute each contribution:

```python
left_choices = i - left[i]
right_choices = right[i] - i
answer += value * left_choices * right_choices
```

Each element contributes as the minimum for exactly that many subarrays.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.sumSubarrayMins([3, 1, 2, 4]) == 17
    assert s.sumSubarrayMins([11, 81, 94, 43, 3]) == 444
    assert s.sumSubarrayMins([1]) == 1
    assert s.sumSubarrayMins([1, 2, 3]) == 10
    assert s.sumSubarrayMins([3, 2, 1]) == 10
    assert s.sumSubarrayMins([2, 2, 2]) == 12

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3, 1, 2, 4]` | Main sample |
| `[11, 81, 94, 43, 3]` | Larger sample |
| `[1]` | Minimum input |
| Increasing array | Minimum often starts at the left |
| Decreasing array | Minimum often appears at the right |
| Equal values | Checks duplicate tie-breaking |