Problem Description

You are given an array of integers arr. For every contiguous subarray of arr, determine the minimum value in that subarray. Return the sum of these minimum values for all possible subarrays, modulo 10^9 + 7.

• The array arr contains n integers, where 1 ≤ arr.length ≤ 3 * 10^4 and 1 ≤ arr[i] ≤ 3 * 10^4.
• You must consider every possible contiguous subarray.
• For each subarray, only the minimum element is counted toward the sum.
• The final answer should be returned modulo 10^9 + 7.

Thought Process

At first glance, you might think about generating all possible subarrays, finding the minimum for each, and summing these values. However, since the number of subarrays is O(n²), this approach is too slow for large arrays.

Instead, we can look for patterns or properties that help us avoid redundant work. The key insight is to determine, for each element, how many subarrays it is the minimum for. If we can efficiently count this for every element, we can multiply each element by its count and sum these products to get the result.

This leads us to think about monotonic stacks, which are often used to find the next or previous smaller elements in an array efficiently.

Solution Approach

The optimized solution uses monotonic stacks to efficiently count, for each element, how many subarrays it is the minimum of. Here's how:

1. For each element in arr:
   • Find the distance to the previous less element (PLE) on the left.
   • Find the distance to the next less element (NLE) on the right.
2. Counting subarrays:
   • For arr[i], the number of subarrays where it is the minimum is left * right, where:
     • left = number of elements between i and its previous less element (including i)
     • right = number of elements between i and its next less element (including i)
   • Multiply arr[i] by left * right and sum over all i.
3. Implementation details:
   • Use a monotonic increasing stack to find previous and next less elements in O(n) time.
   • Carefully handle equal values to avoid double-counting.
   • Take the sum modulo 10^9 + 7 as required.

Example Walkthrough

Let's use the input arr = [3, 1, 2, 4].

1. For each element, we find:
   • 3: Previous less = none, Next less = 1. So, left = 1, right = 1 (distance to next less).
   • 1: Previous less = none, Next less = none (since no smaller element). left = 2 (covers [3,1]), right = 3 (covers [1,2,4]).
   • 2: Previous less = 1, Next less = none. left = 1, right = 2.
   • 4: Previous less = 2, Next less = none. left = 1, right = 1.
2. Calculate contributions:
   • 3: 3 * 1 * 1 = 3
   • 1: 1 * 2 * 3 = 6
   • 2: 2 * 1 * 2 = 4
   • 4: 4 * 1 * 1 = 4
3. Sum: 3 + 6 + 4 + 4 = 17

This matches the expected output.

Code Implementation

class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10 ** 9 + 7
        n = len(arr)
        stack = []
        prev = [None] * n
        next_ = [None] * n

        # Previous less
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)

        stack = []
        # Next less
        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)

        res = 0
        for i in range(n):
            left = i - prev[i]
            right = next_[i] - i
            res = (res + arr[i] * left * right) % MOD
        return res
      

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> prev(n), next(n);
        stack<int> s;

        // previous less
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && arr[s.top()] > arr[i]) s.pop();
            prev[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }

        while (!s.empty()) s.pop();

        // next less
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
            next[i] = s.empty() ? n : s.top();
            s.push(i);
        }

        long res = 0;
        for (int i = 0; i < n; ++i) {
            long left = i - prev[i];
            long right = next[i] - i;
            res = (res + arr[i] * left * right) % MOD;
        }
        return (int)res;
    }
};
      

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;
        int n = arr.length;
        int[] prev = new int[n];
        int[] next = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // previous less
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
            prev[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // next less
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
            next[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long res = 0;
        for (int i = 0; i < n; ++i) {
            long left = i - prev[i];
            long right = next[i] - i;
            res = (res + arr[i] * left * right) % MOD;
        }
        return (int)res;
    }
}
      

var sumSubarrayMins = function(arr) {
    const MOD = 1e9 + 7;
    const n = arr.length;
    const prev = Array(n);
    const next = Array(n);
    const stack = [];

    // Previous less
    for (let i = 0; i < n; ++i) {
        while (stack.length && arr[stack[stack.length-1]] > arr[i]) stack.pop();
        prev[i] = stack.length ? stack[stack.length-1] : -1;
        stack.push(i);
    }

    stack.length = 0;

    // Next less
    for (let i = n - 1; i >= 0; --i) {
        while (stack.length && arr[stack[stack.length-1]] >= arr[i]) stack.pop();
        next[i] = stack.length ? stack[stack.length-1] : n;
        stack.push(i);
    }

    let res = 0;
    for (let i = 0; i < n; ++i) {
        let left = i - prev[i];
        let right = next[i] - i;
        res = (res + arr[i] * left * right) % MOD;
    }
    return res;
};
      

Time and Space Complexity

• Brute-force: O(n²) time and O(1) space (not counting output), since every subarray is considered and minimum is computed for each.
• Optimized (Monotonic Stack): O(n) time and O(n) space.
  • Each element is pushed and popped from the stack at most once.
  • Auxiliary arrays for previous and next less elements require O(n) space.

The optimized approach is efficient and scalable for large input sizes.

Summary

The key to efficiently solving the "Sum of Subarray Minimums" problem is to avoid brute-force enumeration of all subarrays. By realizing that each element's contribution can be counted by the number of subarrays where it is the minimum, and using monotonic stacks to find previous and next less elements, we reduce the problem to linear time. This approach is both elegant and practical, leveraging classic stack techniques to solve a seemingly complex problem with ease.