LeetCode 907: Sum of Subarray Minimums

Problem Restatement

We are given an integer array arr.

For every contiguous subarray, take the minimum value of that subarray.

Return the sum of all those minimum values.

Because the answer can be large, return it modulo:

10**9 + 7

For example:

arr = [3, 1, 2, 4]

All subarray minimums are:

[3]          -> 3
[3, 1]       -> 1
[3, 1, 2]    -> 1
[3, 1, 2, 4] -> 1
[1]          -> 1
[1, 2]       -> 1
[1, 2, 4]    -> 1
[2]          -> 2
[2, 4]       -> 2
[4]          -> 4

The sum is:

3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17

Input and Output

Function shape:

def sumSubarrayMins(arr: list[int]) -> int:
    ...

Examples

Example 1:

arr = [3, 1, 2, 4]

Answer:

17

Example 2:

arr = [11, 81, 94, 43, 3]

Answer:

444

First Thought: Enumerate All Subarrays

A direct method is to generate every subarray and track the minimum.

class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        answer = 0

        for left in range(n):
            current_min = arr[left]

            for right in range(left, n):
                current_min = min(current_min, arr[right])
                answer += current_min

        return answer % MOD

This works, but it has quadratic time complexity.

If arr has length n, there are n * (n + 1) / 2 subarrays.

For large input, this is too slow.

Key Insight

Instead of asking:

“How do we find the minimum of every subarray?”

ask:

“How many subarrays have arr[i] as their minimum?”

If arr[i] is the minimum for count subarrays, then its contribution is:

arr[i] * count

So the answer is the sum of each element’s contribution.

For each index i, we need:

1. How far can we extend left while keeping arr[i] as the minimum?
2. How far can we extend right while keeping arr[i] as the minimum?

Then:

count = left_choices * right_choices

Handling Equal Values

Equal values need careful tie-breaking.

We want each subarray to be assigned to exactly one minimum index.

A common rule is:

• On the left, stop at the previous element strictly less than arr[i].
• On the right, stop at the next element less than or equal to arr[i].

This makes equal values belong consistently to one side and prevents double counting.

For index i:

left[i] = index of previous value < arr[i]
right[i] = index of next value <= arr[i]

Then:

left_choices = i - left[i]
right_choices = right[i] - i

Contribution:

arr[i] * left_choices * right_choices

Algorithm

Use monotonic stacks.

First pass, compute left[i].

For each i, remove stack values that are greater than or equal to arr[i].

After popping, the top is the previous strictly smaller element.

Second pass, compute right[i].

For each i from right to left, remove stack values that are greater than arr[i].

After popping, the top is the next smaller or equal element.

Then sum all contributions.

Correctness

For each index i, left[i] is the nearest index to the left with value strictly less than arr[i].

So any valid subarray where arr[i] is the selected minimum can start at any position from left[i] + 1 through i.

That gives:

i - left[i]

choices.

Similarly, right[i] is the nearest index to the right with value less than or equal to arr[i].

So the subarray can end at any position from i through right[i] - 1.

That gives:

right[i] - i

choices.

Every subarray counted for index i has no smaller value inside it. Also, the tie rule ensures that if multiple equal minimum values exist, exactly one index owns that subarray.

Thus each subarray contributes its minimum value exactly once.

Summing all contributions gives the required answer.

Complexity

Implementation

class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)

        left = [-1] * n
        right = [n] * n

        stack = []

        for i, value in enumerate(arr):
            while stack and arr[stack[-1]] >= value:
                stack.pop()

            if stack:
                left[i] = stack[-1]

            stack.append(i)

        stack = []

        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            if stack:
                right[i] = stack[-1]

            stack.append(i)

        answer = 0

        for i, value in enumerate(arr):
            left_choices = i - left[i]
            right_choices = right[i] - i
            answer += value * left_choices * right_choices

        return answer % MOD

Code Explanation

Initialize boundaries:

left = [-1] * n
right = [n] * n

If no smaller element exists on the left, we use -1.

If no smaller or equal element exists on the right, we use n.

The first stack pass finds the previous strictly smaller value:

while stack and arr[stack[-1]] >= value:
    stack.pop()

After this loop, the stack top is smaller than value, so it becomes left[i].

The second stack pass finds the next smaller or equal value:

while stack and arr[stack[-1]] > arr[i]:
    stack.pop()

After this loop, the stack top has value less than or equal to arr[i], so it becomes right[i].

Finally, compute each contribution:

left_choices = i - left[i]
right_choices = right[i] - i
answer += value * left_choices * right_choices

Each element contributes as the minimum for exactly that many subarrays.

Testing

def run_tests():
    s = Solution()

    assert s.sumSubarrayMins([3, 1, 2, 4]) == 17
    assert s.sumSubarrayMins([11, 81, 94, 43, 3]) == 444
    assert s.sumSubarrayMins([1]) == 1
    assert s.sumSubarrayMins([1, 2, 3]) == 10
    assert s.sumSubarrayMins([3, 2, 1]) == 10
    assert s.sumSubarrayMins([2, 2, 2]) == 12

    print("all tests passed")

run_tests()

Test meaning: