Sum of Subarray Minimums

How it works

We can think of this problem dynamically. Let dp[i] represent the sum of minimums of all subarrays ending at index i. When we add element arr[i], we need to consider: for subarrays where arr[i] is not the minimum, we can reuse previously computed values; for subarrays where arr[i] is the minimum, we count how many such subarrays exist. The stack helps us find where arr[i] stops being the minimum.

Steps

1. Initialize dp array and an empty stack.
2. For each index i:
   • Pop elements from the stack while arr[stack_top] > arr[i].
   • Let j be the stack top after popping (or -1 if empty). This is the index of the previous smaller or equal element.
   • dp[i] = dp[j] + arr[i] * (i - j):
     • dp[j] accounts for subarrays ending before j where arr[i] is not the minimum.
     • arr[i] * (i - j) accounts for subarrays from positions j+1 to i where arr[i] is the minimum.
   • Add dp[i] to res and push i onto the stack.
3. Return res modulo 10^9 + 7.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Double Counting with Duplicate Elements

When there are duplicate values in the array, using strict less-than (<) on both sides when finding previous and next smaller elements causes the same subarray to be counted multiple times. The solution is to use strict less-than (<) on one side and less-than-or-equal (<=) on the other side to ensure each subarray is counted exactly once.

Integer Overflow in Contribution Calculation

The contribution formula arr[i] * left * right can overflow a 32-bit integer when the array is large. With n up to 30,000 and values up to 30,000, the product can reach approximately 2.7 * 10^13. Always use 64-bit integers for the multiplication and apply the modulo operation at each step.

Incorrect Boundary Initialization

When no previous smaller element exists, prevSmaller[i] should be -1 (not 0), representing an imaginary boundary before the array. Similarly, when no next smaller element exists, nextSmaller[i] should be n (not n-1). Using wrong boundary values leads to incorrect counts for subarrays starting at the beginning or ending at the end of the array.

Forgetting to Apply Modulo Operation

The problem requires returning the result modulo 10^9 + 7. A common mistake is only applying modulo at the final return statement. Since intermediate sums can overflow even with 64-bit integers after many additions, modulo should be applied after each addition to the result to keep values within bounds.

from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        dp = [0] * n
        stack, res = [], 0

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

            j = stack[-1] if stack else -1
            dp[i] = (dp[j] if j != -1 else 0) + arr[i] * (i - j)
            dp[i] %= MOD
            res = (res + dp[i]) % MOD
            stack.append(i)

        return res

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> dp(n, 0);
        stack<int> stack;
        long long res = 0;

        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[stack.top()] > arr[i]) {
                stack.pop();
            }

            int j = stack.empty() ? -1 : stack.top();
            dp[i] = ((j != -1 ? dp[j] : 0) + arr[i] * (i - j)) % MOD;
            res = (res + dp[i]) % MOD;
            stack.push(i);
        }

        return res;
    }
};