Sum of Subarray Minimums
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 1
- Core for
- 9 roles
The problem
Given an array of integers, find the sum of the minimum element of every possible contiguous subarray. Since the answer may be large, return it modulo 10^9 + 7.
Example 1
- Input
- arr = [4,2,3,1]
- Output
- 19
- Why
- Subarray minimums sum to 19: [4]=4, [4,2]=2, [4,2,3]=2, [4,2,3,1]=1, [2]=2, [2,3]=2, [2,3,1]=1, [3]=3, [3,1]=1, [1]=1. Total = 4+2+2+1+2+2+1+3+1+1 = 19.
Example 2
- Input
- arr = [7,12,9,4,2]
- Output
- 77
- Why
- Adding up the minimum of each of the fifteen subarrays of [7,12,9,4,2] gives 77.
Constraints
- 1 <= arr.length <= 3 * 10^4
- 1 <= arr[i] <= 3 * 10^4
How to think about it
Updated 2026-09-29Counting subarrays by their bounds is quadratic, but counting elements by their contribution is linear. In how many contiguous subarrays is `arr[i]` the minimum? Exactly `(i - left) * (right - i)`, where `left` and `right` are the nearest strictly smaller elements on either side. Multiplying each element by its valid subarray count sums the entire answer in one pass.
Approaches, worst first
All subarray minimums
time O(n^2) · space O(1)
Fix starting index i, maintain a running minimum as j advances to n - 1, and accumulate the minimum of each `arr[i..j]` into the total. Simple to implement, but quadratic time causes timeout on inputs of length 3 * 10^4.
Monotonic stack for contribution intervalsWrite this one
time O(n) · space O(n)
Find the previous less element and next less element for each index using monotonic stacks. To prevent duplicate counting on identical values, define one boundary with strict inequality `<` and the other with non-strict `<=`. Each element contributes `arr[i] * (i - prev) * (next - i)` modulo 10^9 + 7.
Where people lose marks · 3
- Duplicate values counted twice: if both left and right boundaries use strict `<` (or both use `<=`), subarrays containing duplicate minimums get counted multiple times or omitted entirely; one side must be `<` and the other `<=`.
- Intermediate multiplication overflow: `arr[i] * leftCount * rightCount` can exceed standard 32-bit signed integers before modulo arithmetic is applied; 64-bit integers or BigInt are required.
- Empty boundary fallbacks: if no smaller element exists to the left, use `-1` as the virtual index; if none exists to the right, use `n`.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .