# Sum of Subarray Minimums
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-subarray-minimums)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-subarray-minimums
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Avito](https://scaleengineer.com/companies/avito), [Paytm](https://scaleengineer.com/companies/paytm), [PhonePe](https://scaleengineer.com/companies/phonepe), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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`

# Approaches
## Brute Force Iteration
The most straightforward approach is to simulate the process directly. We can generate every possible contiguous subarray, find the minimum element within each subarray, and then sum up all these minimums. This involves using nested loops to define the start and end points of the subarrays.
**Time:** O(N^2) - There are two nested loops. The outer loop runs N times, and the inner loop runs up to N times for each outer loop iteration. This results in a quadratic time complexity. · **Space:** O(1) - We only use a few variables to store the running sum and current minimum, so the space complexity is constant.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** Highly inefficient for larger arrays.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
This method iterates through all possible starting points `i` of a subarray from `0` to `n-1`. For each starting point `i`, it iterates through all possible ending points `j` from `i` to `n-1`. This pair of `(i, j)` defines a subarray `arr[i...j]`. For each of these subarrays, we find the minimum element and add it to a running total. To find the minimum of `arr[i...j]` efficiently within the loops, we can maintain a variable `currentMin` that is updated as `j` increases.

```java
class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        long totalSum = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            int currentMin = arr[i];
            for (int j = i; j < n; j++) {
                // The minimum of subarray arr[i...j]
                currentMin = Math.min(currentMin, arr[j]);
                totalSum = (totalSum + currentMin) % MOD;
            }
        }

        return (int) totalSum;
    }
}
```
### Algorithm
*   Initialize a variable `totalSum` to 0.
*   Use a nested loop to generate all contiguous subarrays. The outer loop with index `i` will define the start of the subarray, and the inner loop with index `j` will define the end.
*   For each subarray starting at `i`, we can find its minimum as we extend it to the right with the `j` loop.
*   Let `currentMin` be the minimum value in the subarray `arr[i...j]`.
*   In the inner loop, update `currentMin = min(currentMin, arr[j])`.
*   Add this `currentMin` to `totalSum`.
*   Since the sum can be large, perform modulo operation at each addition to prevent overflow: `totalSum = (totalSum + currentMin) % MOD`.
*   After iterating through all subarrays, `totalSum` will hold the final result.

## Monotonic Stack (Two Passes)
A more efficient approach is to change the perspective. Instead of iterating over subarrays, we can iterate over the elements of `arr` and calculate the contribution of each element `arr[i]` to the final sum. The contribution of `arr[i]` is `arr[i]` multiplied by the number of subarrays for which `arr[i]` is the minimum element. This number can be calculated by finding the first element to the left that is smaller than `arr[i]` and the first element to the right that is smaller than or equal to `arr[i]`. These boundaries can be found efficiently using a monotonic stack.
**Time:** O(N) - We make three separate passes through the array (one for `left`, one for `right`, and one for the final sum). Each pass takes O(N) time. Thus, the total time complexity is O(N) + O(N) + O(N) = O(N). · **Space:** O(N) - We use two arrays, `left` and `right`, of size N, and a stack that can grow up to size N in the worst case. Therefore, the space complexity is linear.
**Pros:** Efficient with linear time complexity.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires O(N) extra space for the helper arrays.; Involves multiple passes over the array, which has a slightly higher constant factor than a single-pass solution.
### Explanation
For each element `arr[i]`, we need to find the number of subarrays where it is the minimum. A subarray is defined by a start index `j` and an end index `k`. For `arr[i]` to be the minimum, `j` must be in `(p, i]` and `k` must be in `[i, q)`, where `p` is the index of the first element to the left of `i` that is smaller than `arr[i]` (Previous Less Element, PLE), and `q` is the index of the first element to the right of `i` that is smaller than or equal to `arr[i]` (Next Less or Equal, NLE). This tie-breaking rule (using `<` on the left and `<=` on the right) ensures each subarray is counted exactly once.

The number of choices for `j` is `i - p`, and for `k` is `q - i`. So, `arr[i]` is the minimum in `(i - p) * (q - i)` subarrays. We can compute the PLE and NLE for all elements in O(N) time using two passes with a monotonic stack.

```java
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int MOD = 1_000_000_007;

        // left[i] = number of elements to the left of i (including i)
        // where arr[i] is the minimum.
        int[] left = new int[n];
        // right[i] = number of elements to the right of i (including i)
        // where arr[i] is the minimum.
        int[] right = new int[n];

        Deque<Integer> stack = new ArrayDeque<>();

        // Calculate left boundaries (Previous Less Element)
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            left[i] = i - (stack.isEmpty() ? -1 : stack.peek());
            stack.push(i);
        }

        stack.clear();

        // Calculate right boundaries (Next Less or Equal Element)
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            right[i] = (stack.isEmpty() ? n : stack.peek()) - i;
            stack.push(i);
        }

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

        return (int) totalSum;
    }
}
```
### Algorithm
*   The core idea is to calculate the contribution of each element `arr[i]` to the total sum.
*   An element `arr[i]` is the minimum in any subarray `arr[j...k]` where `j <= i <= k` and all other elements in `arr[j...k]` are greater than or equal to `arr[i]`.
*   To handle duplicates correctly and avoid overcounting, we can establish a rule: `arr[i]` is the designated minimum if it's the *leftmost* minimum in the subarray. This means elements to its left must be strictly greater, and elements to its right can be greater than or equal.
*   This translates to finding the boundaries for each `arr[i]`: the index of the **Previous Less Element** (`p`) and the **Next Less Element** (`q`).
*   The number of subarrays where `arr[i]` is the minimum is `(i - p) * (q - i)`.
*   We can find the `p` and `q` for all elements efficiently using a monotonic stack in two separate passes.
    1.  **First Pass (left to right):** Find the Previous Less Element (PLE) for each element. Let's call the result `left` array where `left[i] = i - p`.
    2.  **Second Pass (right to left):** Find the Next Less or Equal Element (NLE) for each element. Let's call the result `right` array where `right[i] = q - i`.
*   Finally, iterate through the array one more time, and for each `i`, add `arr[i] * left[i] * right[i]` to the total sum, taking the modulo at each step.

## Optimized Monotonic Stack (Single Pass)
This is the most optimized approach, building upon the monotonic stack concept. Instead of using two passes to precompute the left and right boundaries, we can calculate an element's contribution to the total sum at the exact moment it is popped from the stack. This allows us to solve the problem in a single pass.
**Time:** O(N) - Each index is pushed onto and popped from the stack at most once. This results in a single pass and linear time complexity. · **Space:** O(N) - In the worst-case scenario (a strictly increasing array), the stack can hold all N indices.
**Pros:** Most efficient solution with O(N) time complexity.; Requires only a single pass over the array.; Saves space by not needing explicit `left` and `right` arrays.
**Cons:** The logic can be less intuitive to understand compared to the two-pass approach.
### Explanation
We maintain a monotonically increasing stack of indices. When we encounter a new element `arr[i]` that is smaller than the element at the top of the stack, `arr[j]`, it means `arr[i]` is the first smaller element to the right of `arr[j]` (its Next Less Element). The element `arr[k]` that was below `arr[j]` on the stack is the first smaller or equal element to its left (its Previous Less or Equal Element). With these two boundaries (`k` and `i`), we can calculate the number of subarrays where `arr[j]` is the minimum and add its contribution to the total sum. We process all such `j`'s from the stack before pushing `i`. A sentinel value (like 0) is conceptually added at the end of the array to ensure any elements remaining in the stack are popped and processed.

```java
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int MOD = 1_000_000_007;
        long totalSum = 0;

        // Stack stores indices of elements in increasing order of their values.
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i <= n; i++) {
            // Use a sentinel value (0) at the end to pop all remaining elements.
            int currentVal = (i == n) ? 0 : arr[i];

            while (!stack.isEmpty() && arr[stack.peek()] > currentVal) {
                int j = stack.pop(); // j is the index of the minimum element
                int k = stack.isEmpty() ? -1 : stack.peek(); // k is the index of the Previous Less Element
                
                // i is the index of the Next Less Element
                long leftCount = j - k;
                long rightCount = i - j;

                long contribution = (long) arr[j] * leftCount * rightCount;
                totalSum = (totalSum + contribution) % MOD;
            }
            stack.push(i);
        }

        return (int) totalSum;
    }
}
```
### Algorithm
*   Initialize an empty monotonic stack (to store indices), and `totalSum = 0`.
*   Iterate through the array from `i = 0` to `n` (inclusive). The `n`-th iteration is for a conceptual sentinel value (0) to ensure all elements remaining in the stack are processed.
*   In each iteration `i`, let `currentVal` be `arr[i]` (or 0 if `i == n`).
*   While the stack is not empty and the element at the stack's top index `j` is greater than `currentVal`:
    *   This means `currentVal` (at index `i`) is the **Next Less Element (NLE)** for `arr[j]`.
    *   Pop `j` from the stack.
    *   The element now at the top of the stack, `k`, is the **Previous Less or Equal Element (PLE)** for `arr[j]`.
    *   Calculate the contribution of `arr[j]`: `contribution = arr[j] * (j - k) * (i - j)`.
    *   Add this contribution to `totalSum` (with modulo).
*   After the while loop, push the current index `i` onto the stack.
*   After the main loop finishes, `totalSum` will hold the result.

# Solutions
### Java

```java
class Solution {
public
  int sumSubarrayMins(int[] arr) {
    int n = arr.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && arr[stk.peek()] > arr[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    final int mod = (int)1 e9 + 7;
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += (long)(i - left[i]) * (right[i] - i) % mod * arr[i] % mod;
      ans %= mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution { public: int sumSubarrayMins ( vector < int >& arr ) { int n = arr . size (); vector < int > left ( n , - 1 ); vector < int > right ( n , n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { while ( ! stk . empty () && arr [ stk . top ()] >= arr [ i ]) { stk . pop (); } if ( ! stk . empty ()) { left [ i ] = stk . top (); } stk . push ( i ); } stk = stack < int > (); for ( int i = n - 1 ; i >= 0 ; -- i ) { while ( ! stk . empty () && arr [ stk . top ()] > arr [ i ]) { stk . pop (); } if ( ! stk . empty ()) { right [ i ] = stk . top (); } stk . push ( i ); } long long ans = 0 ; const int mod = 1e9 + 7 ; for ( int i = 0 ; i < n ; ++ i ) { ans += 1LL * ( i - left [ i ]) * ( right [ i ] - i ) * arr [ i ] % mod ; ans %= mod ; } return ans ; } };
```

### Python

```python
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int: n = len(arr) left = [- 1] * n right = [n] * n stk = [] for i, v in enumerate(arr): while stk and arr[stk[- 1]] >= v: stk . pop() if stk: left[i] = stk[- 1] stk . append(i) stk = [] for i in range(n - 1, - 1, - 1): while stk and arr[stk[- 1]] > arr[i]: stk . pop() if stk: right[i] = stk[- 1] stk . append(i) mod = 10 ** 9 + 7 return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod

```