Sum of Subarray Minimums Medium 0 attempts
LeetCode ↗

Sum of Subarray Minimums

Medium Stack&Queue LeetCode

Given an array of integers, look at every contiguous subarray, take its minimum value, and add all those minimums together. Return the total modulo 10^9+7.

Input Format
Implement sumSubarrayMins(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [3,1,2,4]
Output
17

Example 2

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

Monotonic Stack (Contribution)

javascript
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