LeetCode #907 Medium

Sum of Subarray Minimums

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

monotonic-stackarraycontribution

02

Intuition

💡

It is tempting to give every tied minimum its own boundary using strictly-smaller comparisons on both sides, but then two equal elements both think they own the subarray between them and the total comes out too high. Do not iterate over subarrays — iterate over elements, and for each ask: in how many subarrays am I the minimum, counted once? That count is left * right, where left is the distance to the previous smaller element and right the distance to the next smaller-or-equal — the asymmetry is what stops the double count. Multiply by the value, sum over all elements, and every subarray is accounted for exactly once. This is the contribution technique, and monotonic stacks compute both distances in O(n).

03

Approach

1

Invert the loop

There are O(n^2) subarrays, so summing per subarray is already too slow before you even find each minimum. Instead, each element nums[i] contributes nums[i] once for every subarray where it is the minimum, so the answer is the sum of nums[i] * count(i).

2

Count the subarrays where i is the minimum

Let pse be the index of the previous strictly-smaller element and nse the index of the next smaller. Any subarray whose start lies in (pse, i] and whose end lies in [i, nse) has nums[i] as its minimum. That gives (i - pse) * (nse - i) subarrays — a product of two independent choices.

3

Break ties on exactly one side

With duplicate values, using strictly-smaller comparisons on both pse and nse makes every tied element count some of the same subarrays as its twin, and the sum comes out too big. Fix it by making one side strict and the other non-strict: previous strictly smaller, next smaller-or-equal. Now a run of equal values gets split cleanly — each subarray spanning them is credited to exactly one, whichever one the non-strict side stops at. Both boundary arrays come from monotonic stacks in O(n); take everything mod 1e9+7. Sum of Subarray Ranges is the same code run twice, once for minima and once for maxima, subtracted.

04

Solution & live demo

python

▶1class Solution:
▶2    def sumSubarrayMins(self, arr):
▶3        MOD = 10 ** 9 + 7
▶4        n = len(arr)
▶5        pse, nse = [-1] * n, [n] * n
▶6        st = []
▶7        for i in range(n):
▶8            while st and arr[st[-1]] >= arr[i]:
▶9                st.pop()
▶10            pse[i] = st[-1] if st else -1
▶11            st.append(i)
▶12        st = []
▶13        for i in range(n - 1, -1, -1):
▶14            while st and arr[st[-1]] > arr[i]:
▶15                st.pop()
▶16            nse[i] = st[-1] if st else n
▶17            st.append(i)
▶18        total = 0
▶19        for i in range(n):
▶20            total += arr[i] * (i - pse[i]) * (nse[i] - i)
▶21        return total % MOD

05

Edge cases

All elements equal

The strict/non-strict asymmetry is exactly what stops double counting here — the case worth hand-checking.

Strictly increasing array

Every element is the minimum only of subarrays starting at itself, so left is always 1.

Single element

One subarray, so the answer is that element.

Overflow

Sums exceed 64-bit range for large inputs, so apply the modulus as you accumulate.

06

Complexity

Time

O(n)

Space

O(n)

Two monotonic-stack passes plus a linear sum, replacing the O(n^2) subarray enumeration.