AlgoViz
HomeStack

Sum of Subarray Minimums

Medium

Count the subarrays each element dominates

Problem

Return the sum of the minimum of every contiguous subarray, modulo 1e9+7.

In simple words

For each element, count how many subarrays it is the minimum of, then weight it by that count.

The idea

Instead of enumerating subarrays, ask for each element how many subarrays it is the minimum of — that is (distance to the previous smaller) × (distance to the next smaller). A monotonic stack finds both boundaries in O(n).

The trick

  • Contribution = value × left span × right span.
  • Break ties on one side only (strict on one, non-strict on the other) or subarrays are double-counted.
  • Take the modulus as you accumulate; the total overflows quickly.
3
1
2
4
0
1
2
3

Step 1 of 12. Brute force: for every subarray, add its minimum to the total. Values: 3, 1, 2, 4.

1/12
Brute force
timeO(n²)spaceO(1)

Min of every subarray.

1for (let i = 0; i < n; i++) {2  let mn = Infinity;3  for (let j = i; j < n; j++) { mn = Math.min(mn, nums[j]); total += mn; }4}

Input

array
[3, 1, 2, 4]

Output

total
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [3, 1, 2, 4]
Output:
17
Explanation:
Add up the minimum of every subarray → 17.

Example 2

Input:
nums = [1, 2, 3]
Output:
10
Explanation:
Sum of all subarray minimums is 10.

Example 3

Input:
nums = [2, 2]
Output:
6
Explanation:
Mins: 2,2,2 → 6.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.