Sum of Subarray Minimums

Given an array arr, consider every contiguous subarray and take its minimum element. Return the sum of all those minimums. Because the answer can be large, return it modulo 10^9 + 7.

Hints

· Stuck? Reveal one nudge at a time.

Enumerating subarrays is O(n^2). Instead, ask: for each element, how many subarrays is it the minimum of?

That count is (distance to previous smaller) x (distance to next smaller).

Use strict on one side and non-strict on the other to count equal minimums exactly once.

Common doubts

Each subarray has exactly one minimum, so summing (value x number-of-subarrays-it-minimizes) over elements equals the total — and each count is O(1) with the boundaries.

Without the asymmetry, a run of equal minimums would credit the same subarray to multiple elements (or none). Strict-on-one-side attributes each subarray to a single index.

value x left x right can exceed 32 bits; accumulate in 64-bit (or BigInt) and take the result modulo 1e9+7.

Interview follow-ups

· What an interviewer asks next.

Mirror it — use previous/next greater boundaries instead of smaller.

Range = max - min per subarray, so sum of ranges = (sum of maximums) - (sum of minimums), each computed this way.

Fun facts

The 'each element contributes value x span-left x span-right' identity is the backbone of many subarray-aggregate problems.
The strict/non-strict tie-break is a subtle but classic source of off-by-one bugs — worth internalizing once.

Asked at

AmazonGoogleMeta

Frequently Sometimes Occasionally

Example 1

Input: arr = [3,1,2,4]
Output: 17
Subarray minimums are 3,1,2,4,1,1,2,1,1,2; their sum is 17.

Example 2

Input: arr = [11,81,94,43,3]
Output: 444
Summing the minimum of all 15 subarrays gives 444.

Constraints

- 1 <= arr.length <= 3 * 10^4 - 1 <= arr[i] <= 3 * 10^4

Instead of iterating over the O(n^2) subarrays, flip the question: for each element, in how many subarrays is it the minimum? Its total contribution is value x (that count), and the count is (elements it extends left) x (elements it extends right) — found with a monotonic stack via the previous-smaller and next-smaller boundaries.

Prerequisites

Before you start

· Concepts used directly in the solution.

Contribution technique. Summing each element's value times the number of subarrays it dominates, rather than enumerating subarrays.

Previous/next smaller. Monotonic-stack boundaries that delimit where an element stays the minimum.

Strict / non-strict tie-break. Using strictly-smaller on one side and smaller-or-equal on the other to count equal elements exactly once.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Counting

“Why not just enumerate subarrays?”

There are O(n^2) of them; the contribution view is O(n).

“How are duplicate minimums handled?”

By making one boundary strict and the other non-strict, each subarray is credited to exactly one element.

The ideal opening — say it like this

I'll count, for each element, how many subarrays it's the minimum of, then multiply by its value.

That count is the span to the previous strictly-smaller element times the span to the next smaller-or-equal.

Two monotonic-stack passes give those boundaries in O(n), and I sum value times left times right mod 1e9+7.

Understand the problem

Worked example — arr = [3, 1, 2, 4], focus on the 1 at index 1

previous strictly smaller than 1: none -> boundary at index -1 -> left = 1 - (-1) = 2
next smaller-or-equal to 1: none      -> boundary at index 4  -> right = 4 - 1 = 3
1 is the min of 2 x 3 = 6 subarrays -> contributes 1 * 6 = 6

Key observations

1Aha

Count subarrays each element dominates

arr[i] is the min of left x right subarrays, where left/right are the distances to the nearest smaller elements on each side. Its contribution is arr[i] x left x right.

2Aha

Break ties with strict on one side only

Using "previous strictly smaller" and "next smaller-or-equal" (or vice versa) ensures each subarray's minimum is attributed to exactly one index even with duplicates.

3Aha

Two stack passes, O(n)

A left-to-right pass finds previous-smaller; a right-to-left pass finds next-smaller-or-equal. Each element is pushed and popped once.

Brute force vs optimal

	Every subarray	Contribution via stack
Idea	Track the running min of each subarray	Count subarrays each element is the min of
Time	O(n^2)	O(n)
Space	O(1)	O(n)

Full code is in the Approaches selector below.

Summary

Key takeaway

Sum each element's contribution: arr[i] x left x right, where left and right are the distances to the previous strictly-smaller and next smaller-or-equal elements (found by two monotonic-stack passes). The strict/non-strict asymmetry avoids double-counting equal minimums. O(n), mod 1e9+7.

prev_less[i]: index of previous strictly smaller (monotonic stack)
next_le[i]:   index of next smaller-or-equal   (monotonic stack)
answer = sum arr[i] * (i - prev_less[i]) * (next_le[i] - i)  mod 1e9+7