Sum of Subarray Minimums — Solution in Python, Java & C++
Sum of Subarray Minimums solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Subarray Minimums is a medium coding problem on arrays, dynamic programming and stack, asked in Amazon, Google, Bloomberg and Sprinklr interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Stack, Monotonic Stack
- Asked at: Amazon, Google, Bloomberg, Sprinklr, Hulu
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers arr, return the sum of min(b) over every contiguous non-empty subarray b of arr.
Because the answer can be large, return it modulo 10^9 + 7.
Example 1
Input: arr = [3,1,2,4]
Output: 17
Explanation: The minima are 3,1,2,4,1,1,2,1,1,1 — summing to 17.
Example 2
Input: arr = [11,81,94,43,3]
Output: 444
Example 3
Input: arr = [1]
Output: 1
Constraints
1 <= arr.length <= 1001 <= arr[i] <= 10000
Follow-up: The brute force is O(n²). Can you count each element's contribution in O(n) with a monotonic stack?
Hints for Sum of Subarray Minimums
Hint 1
Instead of enumerating subarrays, ask how many subarrays each element is the minimum of.
Hint 2
For index
i, letleft[i]be the number of choices for the subarray's start andright[i]the choices for its end; the contribution isarr[i] * left[i] * right[i].Hint 3
Use a strict comparison on one side and a non-strict one on the other so equal values are not double counted.
How to solve Sum of Subarray Minimums
Count how many subarrays each element is the minimum of: left[i] choices of start, right[i] choices of end, found with two monotonic-stack passes using strict/non-strict comparisons to break ties.
Approach
- Left pass: pop while
arr[top] > arr[i];left[i] = i - top(ori + 1). - Right pass: pop while
arr[top] >= arr[i];right[i] = top - i(orn - i). - Sum
arr[i] · left[i] · right[i]modulo10⁹ + 7.
Why it works
left[i] is the distance to the previous strictly smaller element and right[i] the distance to the next smaller-or-equal one, so arr[i] is the minimum of exactly left[i] · right[i] subarrays with equal minima assigned to exactly one index.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Using the same comparison on both sides double-counts subarrays with repeated minima.
Reference solution
Python
def sumSubarrayMins(arr) -> int:
MOD = 1000000007
n = len(arr)
left = [0] * n
right = [0] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
left[i] = i + 1 if not stack else 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()
right[i] = n - i if not stack else stack[-1] - i
stack.append(i)
total = 0
for i in range(n):
total = (total + arr[i] * left[i] * right[i]) % MOD
return totalJava
public static int sumSubarrayMins(int[] arr) {
final int MOD = 1000000007;
int n = arr.length;
int[] left = new int[n];
int[] right = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
stack.push(i);
}
long total = 0;
for (int i = 0; i < n; i++) {
total = (total + (long) arr[i] * left[i] * right[i]) % MOD;
}
return (int) total;
}C++
int sumSubarrayMins(vector<int>& arr) {
const long long MOD = 1000000007LL;
int n = (int) arr.size();
vector<int> left(n, 0), right(n, 0);
vector<int> stack;
for (int i = 0; i < n; i++) {
while (!stack.empty() && arr[stack.back()] > arr[i]) stack.pop_back();
left[i] = stack.empty() ? i + 1 : i - stack.back();
stack.push_back(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && arr[stack.back()] >= arr[i]) stack.pop_back();
right[i] = stack.empty() ? n - i : stack.back() - i;
stack.push_back(i);
}
long long total = 0;
for (int i = 0; i < n; i++) {
total = (total + (long long) arr[i] * left[i] * right[i]) % MOD;
}
return (int) total;
}JavaScript
var sumSubarrayMins = function(arr) {
const MOD = 1000000007;
const n = arr.length;
const left = [], right = [];
for (let i = 0; i < n; i++) {
left.push(0);
right.push(0);
}
let stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) stack.pop();
left[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
stack.push(i);
}
stack = [];
for (let i = n - 1; i >= 0; i--) {
while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) stack.pop();
right[i] = stack.length === 0 ? n - i : stack[stack.length - 1] - i;
stack.push(i);
}
let total = 0;
for (let i = 0; i < n; i++) {
total = (total + arr[i] * left[i] * right[i]) % MOD;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming