Problem Statement
Sum of Subarray Minimums
A subarray is just a slice of the array that you cut out without skipping anything, like grabbing a few items in a row. For every possible slice, we look at the smallest number in it, and we add all those smallest numbers together. The answer can get huge, so we give the leftover after dividing by 10^9 + 7 (this is called taking the result modulo a number, a way to keep big sums small). The slow way is to look at every slice and find its minimum, which takes O(n²) time, meaning the work grows with the square of how many items there are. There is a faster way using a tool called a monotonic stack. A stack is like a pile of plates: you add to the top and take from the top, so the last thing in is the first thing out. "Monotonic" just means we keep the pile in order, smallest at the bottom going up. Here is the trick that makes it fast: instead of asking "what is the minimum of each slice," we flip the question and ask, for each number, "in how many slices am I the smallest one?" If arr[i] is the smallest in some slices, it adds arr[i] times (how many such slices) to the total.
Signals to notice
Brute force first
Enumerate all subarrays, find each minimum. Each subarray independently finds its minimum. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
For each element, count how many subarrays it's the minimum of. Use monotonic stacks to find the distance to the previous and next smaller elements. Contribution = nums[i] × left × right. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on arr = [3, 1, 2, 4]
LEFT pass (>=, pop on tie). i=0 arr=3: stack empty -> left[0]=0+1=1; stack=[0] i=1 arr=1: pop 0 (3>=1) -> empty -> left[1]=1+1=2; stack=[1] i=2 arr=2: top=1 arr=1, 1>=2 false -> left[2]=2-1=1; stack=[1,2] i=3 arr=4: top=2 arr=2, 2>=4 false -> left[3]=3-2=1; stack=[1,2,3]. left=[1,2,1,1] RIGHT pass (strict >, keep on tie). i=3 arr=4: empty -> right[3]=n-i=4-3=1; stack=[3] i=2 arr=2: pop 3 (4>2) -> empty -> right[2]=4-2=2; stack=[2]. i=1 arr=1: pop 2 (2>1) -> empty -> right[1]=4-1=3; stack=[1] i=0 arr=3: top=1 arr=1, 1>3 false -> right[0]=1-0=1; stack=[1,0]. right=[1,3,2,1] Contributions arr[i]*left[i]*right[i]: 3*1*1=3, 1*2*3=6, 2*1*2=4, 4*1*1=4 Sum = 3+6+4+4 = 17; 17 % (1e9+7) = 17 -> return 17
What must stay true
Element nums[i] is the minimum of all subarrays starting in [prevSmaller+1, i] and ending in [i, nextSmaller-1]. The count of such subarrays is left × right, where left and right are the distances to the boundaries. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
for i in 0..n: while stack and arr[top] >= arr[i]: pop; left[i] = i - top (or i+1 if empty); push i for i in n-1..0: while stack and arr[top] > arr[i]: pop; right[i] = top - i (or n-i if empty); push i answer = sum( arr[i] * left[i] * right[i] ) % MOD
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Handling equal elements — use strict < on one side and ≤ on the other to avoid double-counting subarrays where multiple elements share the minimum value. The fix is usually to return to the meaning of each move, not just the steps themselves.