Skip to main content

Sum of Subarray Minimums

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 10^9 + 7.

Constraints:
  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4
Examples
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 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17
Example 2:
Input: arr = [11,81,94,43,3]
Output: 444

Solution​

Approach: Monotonic Stack (Contribution Method)​

The key insight is to think about the contribution of each element to the final sum, rather than iterating through all possible subarrays.

For each element arr[i], we need to count how many subarrays have arr[i] as their minimum value. If we can determine:

  • left[i]: the index of the first element to the left that is smaller than arr[i]
  • right[i]: the index of the first element to the right that is smaller than or equal to arr[i]

Then the number of subarrays where arr[i] is the minimum is:

count = (i - left[i]) × (right[i] - i)

The contribution of arr[i] to the final sum is:

contribution = arr[i] × count

Why use "smaller" on the left and "smaller or equal" on the right? This prevents double-counting when there are duplicate minimum values in a subarray.

Algorithm Steps:

  1. Use a monotonic increasing stack to find left[i] for each element
  2. Use another monotonic increasing stack to find right[i] for each element
  3. Calculate each element's contribution and sum them up

Time Complexity: O(n) - Each element is pushed and popped from the stack at most once Space Complexity: O(n) - For the left, right arrays and the stack

function sumSubarrayMins(arr: number[]): number {
  const MOD = 10 ** 9 + 7;
  const n = arr.length;

  // left[i]: index of first smaller element to the left (-1 if none)
  // right[i]: index of first smaller or equal element to the right (n if none)
  const left: number[] = new Array(n).fill(-1);
  const right: number[] = new Array(n).fill(n);

  // Monotonic increasing stack to find left boundaries
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
      stack.pop();
    }
    if (stack.length > 0) {
      left[i] = stack[stack.length - 1];
    }
    stack.push(i);
  }

  // Clear stack and find right boundaries
  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
      stack.pop();
    }
    if (stack.length > 0) {
      right[i] = stack[stack.length - 1];
    }
    stack.push(i);
  }

  // Calculate the sum of contributions
  let result = 0;
  for (let i = 0; i < n; i++) {
    const leftCount = i - left[i];
    const rightCount = right[i] - i;
    result = (result + arr[i] * leftCount * rightCount) % MOD;
  }

  return result;
}

Example Walkthrough​

For arr = [3, 1, 2, 4]:

IndexValueleft[i]right[i]leftCountrightCountContribution
03-11113 × 1 × 1 = 3
11-14231 × 2 × 3 = 6
2214122 × 1 × 2 = 4
3424114 × 1 × 1 = 4

Sum = 3 + 6 + 4 + 4 = 17 ✓