Sum of Subarray Minimums Medium 0 attempts
LeetCode ↗

Sum of Subarray Minimums

Medium Stack&Queue LeetCode

Given an array of integers, find the sum of min(subarray) for all contiguous subarrays. Return modulo 10^9+7.

Example: arr = [3,1,2,4] → Output: 17

Sample Input
—
Sample Output
—
Constraints
  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4
Test Cases
Case 1
Args: [[3,1,2,4]] Expected: 17
Topics
Stack&Queue

Monotonic Stack (Contribution)

function sumSubarrayMins(arr) {
  const MOD = 1e9+7, n = arr.length, stack = [];
  let sum = 0;
  for (let i = 0; i <= n; i++) {
    while (stack.length && (i===n || arr[stack[stack.length-1]] >= arr[i])) {
      const j = stack.pop();
      const left = stack.length ? j - stack[stack.length-1] : j + 1;
      const right = i - j;
      sum = (sum + arr[j] * left * right) % MOD;
    }
    stack.push(i);
  }
  return sum;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript