Sum of Subarray Minimums solution and explanation
Google
9 more videos on this problem
L9. Sum of Subarray Minimum | Stack and Queue Playlisttake U forward · 23:35 · 351K views
Leetcode 907. Sum of Subarray MinimumsFraz · 9:43 · 91K views
Sum of Subarray Minimums - Leetcode 907 - PythonNeetCodeIO · 18:51 · 56K views
Sum of Subarray Minimums | Detailed | Leetcode 907codestorywithMIK · 49:39 · 54K views
907. Sum of Subarray Minimums | Monotonic Stack | Brute - Better - OptimalAryan Mittal · 31:06 · 22K views
Leetcode 907 Sum of Subarray Minimums | Monotonic Stacks | Coding Decoded SDE SheetCoding Decoded · 7:55 · 13K views
LeetCode 907. Sum of Subarray MinimumsHappy Coding · 24:02 · 9K views
✅ Sum of Subarray Minimums - LeetCode 907 - Monotonic Stack - Prefix Sum - Arrays - ExplainedLeet Logics · 13:07 · 8K views
WALKTHROUGH - LeetCode 907. Sum of Subarray MinimumsKacy Codes · 28:12 · 3K views
Sum of Subarray Minimums - Stack - Python - Leetcode 907CheatCode Ninja · 10:10 · 2K views
The problem
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.
Example 1:
Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
Example 2:
Input: arr = [11,81,94,43,3] Output: 444
Constraints:
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
Approach overview
Problem Overview: Given an integer array arr, compute the sum of the minimum value of every possible subarray. A brute force enumeration would check all subarrays and track the minimum, but that becomes too slow for large inputs. The key insight is counting how many subarrays treat a specific element as the minimum.
Approach 1: Dynamic Programming with Previous Less Element (O(n) time, O(n) space)
This method combines dynamic programming with a stack that tracks the previous smaller element. For each index i, compute how many subarrays ending at i use arr[i] as the minimum. If prevLess is the nearest index to the left with a smaller value, then the contribution depends on the distance i - prevLess. A DP array stores the total contribution for subarrays ending at each index, allowing reuse of previously computed values instead of recomputing minimums. This approach reduces repeated work and builds the final answer incrementally while scanning the array once.
Approach 2: Monotonic Stack Contribution Counting (O(n) time, O(n) space)
The optimal solution uses a monotonic stack to determine the range where each element acts as the minimum. Maintain an increasing stack of indices. For every element, compute two distances: how far it can extend to the left before encountering a smaller value, and how far it can extend to the right before a strictly smaller element appears. If left represents the number of choices on the left and right on the right, the element contributes arr[i] * left * right to the total sum. Each index is pushed and popped at most once, giving linear time. This pattern appears frequently in problems involving range dominance and nearest smaller elements in an array stack workflow.
Recommended for interviews: Interviewers expect the monotonic stack solution. It demonstrates understanding of nearest-smaller-element patterns and contribution counting, both common in advanced array questions. Showing the dynamic programming interpretation first can help explain the idea, but implementing the O(n) monotonic stack approach proves you can translate the insight into an efficient solution.
Approach 1: Monotonic Stack Approach
The monotonic stack approach leverages a stack data structure to efficiently determine the minimum element of every subarray. By maintaining indexes and utilizing their properties, we can efficiently compute the sum of all minimum values for the contiguous subarrays.
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
stack = []
result = 0
for i in range(n + 1):
while stack and (i == n or arr[stack[-1]] >= arr[i]):
cur_index = stack.pop()
cur_value = arr[cur_index]
left = cur_index - stack[-1] if stack else cur_index + 1
right = i - cur_index
result += cur_value * left * right
result %= MOD
stack.append(i)
return resultimport java.util.Stack;
public class Solution {
public int sumSubarrayMins(int[] arr) {
long MOD = (long)1e9 + 7;
int n = arr.length;
Stack<Integer> stack = new Stack<>();
long sum = 0;
for (int i = 0; i <= n; i++) {
while (!stack.isEmpty() && (i == n || arr[stack.peek()] >= arr[i])) {
int index = stack.pop();
int curValue = arr[index];
int left = stack.isEmpty() ? index + 1 : index - stack.peek();
int right = i - index;
sum += (long)curValue * left * right;
sum %= MOD;
}
stack.push(i);
}
return (int)sum;
}
}#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
const ll MOD = 1e9 + 7;
int n = arr.size();
vector<int> left(n), right(n);
stack<int> s1, s2;
for (int i = 0; i < n; i++) {
while (!s1.empty() && arr[s1.top()] > arr[i]) s1.pop();
left[i] = (s1.empty()) ? (i + 1) : (i - s1.top());
s1.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!s2.empty() && arr[s2.top()] >= arr[i]) s2.pop();
right[i] = (s2.empty()) ? (n - i) : (s2.top() - i);
s2.push(i);
}
ll result = 0;
for (int i = 0; i < n; i++) {
result = (result + (ll)arr[i] * left[i] * right[i]) % MOD;
}
return (int)result;
}
};const sumSubarrayMins = (arr) => {
const MOD = 1e9 + 7;
const n = arr.length;
const stack = [];
let result = 0;
for (let i = 0; i <= n; i++) {
while (stack.length > 0 && (i === n || arr[stack[stack.length - 1]] >= arr[i])) {
const curIndex = stack.pop();
const curValue = arr[curIndex];
const left = stack.length > 0 ? curIndex - stack[stack.length - 1] : curIndex + 1;
const right = i - curIndex;
result = (result + curValue * left * right) % MOD;
}
stack.push(i);
}
return result;
};#include <stdio.h>
#define MOD 1000000007
#define MAX 30000
int sumSubarrayMins(int* arr, int arrSize) {
long res = 0;
int stack[MAX], top = -1;
int left[MAX], right[MAX];
for (int i = 0; i < arrSize; ++i) {
while (top != -1 && arr[stack[top]] > arr[i]) --top;
left[i] = (top == -1) ? i + 1 : i - stack[top];
stack[++top] = i;
}
top = -1;
for (int i = arrSize - 1; i >= 0; --i) {
while (top != -1 && arr[stack[top]] >= arr[i]) --top;
right[i] = (top == -1) ? arrSize - i : stack[top] - i;
stack[++top] = i;
}
for (int i = 0; i < arrSize; ++i) {
res = (res + (long)arr[i] * left[i] * right[i]) % MOD;
}
return (int)res;
}using System;
using System.Collections.Generic;
public class Solution {
public int SumSubarrayMins(int[] arr) {
const int MOD = (int)1e9 + 7;
int n = arr.Length;
Stack<int> stack = new Stack<int>();
long sum = 0;
for (int i = 0; i <= n; i++) {
while (stack.Count > 0 && (i == n || arr[stack.Peek()] >= arr[i])) {
int index = stack.Pop();
int curValue = arr[index];
int left = stack.Count == 0 ? index + 1 : index - stack.Peek();
int right = i - index;
sum = (sum + (long)curValue * left * right) % MOD;
}
stack.Push(i);
}
return (int)sum;
}
}This Python solution efficiently computes the result by leveraging the stack to find contributions of each element iteratively to the final sum as the minimum of subarrays.
Time Complexity: O(n), where n is the array size.
Space Complexity: O(n) due to stacking operations.
Approach 2: Dynamic Programming Approach
A dynamic programming approach can also be adopted to tackle the given problem. This method involves calculating the contribution of each element to subarray minimums utilizing previously calculated results intelligently.
def sumSubarrayMins(arr):
MOD = 10**9 + 7
n = len(arr)
dp = [0] * n
stack = []
result = 0
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
k = (i - stack[-1]) if stack else (i + 1)
dp[i] = (arr[i] * k + (dp[stack[-1]] if stack else 0)) % MOD
result = (result + dp[i]) % MOD
stack.append(i)
return resultimport java.util.Stack;
public class Solution {
public int sumSubarrayMins(int[] arr) {
int MOD = (int)1e9 + 7;
int n = arr.length;
int[] dp = new int[n];
Stack<Integer> stack = new Stack<>();
long result = 0;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
int k = (!stack.isEmpty() ? i - stack.peek() : i + 1);
dp[i] = (arr[i] * k + (!stack.isEmpty() ? dp[stack.peek()] : 0)) % MOD;
result = (result + dp[i]) % MOD;
stack.push(i);
}
return (int)result;
}
}#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int MOD = 1e9 + 7;
int n = arr.size();
vector<int> dp(n);
stack<int> s;
ll result = 0;
for (int i = 0; i < n; ++i) {
while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
int k = (s.empty()) ? i + 1 : i - s.top();
dp[i] = (arr[i] * k + (s.empty() ? 0 : dp[s.top()])) % MOD;
result = (result + dp[i]) % MOD;
s.push(i);
}
return (int)result;
}
};const sumSubarrayMins = (arr) => {
const MOD = 1e9 + 7;
const n = arr.length;
const dp = new Array(n).fill(0);
const stack = [];
let result = 0;
for (let i = 0; i < n; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
stack.pop();
}
const k = stack.length > 0 ? i - stack[stack.length - 1] : i + 1;
dp[i] = arr[i] * k + (stack.length > 0 ? dp[stack[stack.length - 1]] : 0);
dp[i] %= MOD;
result += dp[i];
result %= MOD;
stack.push(i);
}
return result;
};#include <stdio.h>
#define MOD 1000000007
int sumSubarrayMins(int* arr, int arrSize) {
int dp[arrSize];
int stack[arrSize], top = -1;
int result = 0;
for (int i = 0; i < arrSize; ++i) {
while (top >= 0 && arr[stack[top]] >= arr[i]) top--;
int k = (top == -1) ? i + 1 : i - stack[top];
dp[i] = arr[i] * k + ((top == -1) ? 0 : dp[stack[top]]);
dp[i] %= MOD;
result = (result + dp[i]) % MOD;
stack[++top] = i;
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int SumSubarrayMins(int[] arr) {
int MOD = (int)1e9 + 7;
int n = arr.Length;
int[] dp = new int[n];
Stack<int> stack = new Stack<int>();
long result = 0;
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) stack.Pop();
int k = (stack.Count > 0) ? i - stack.Peek() : i + 1;
dp[i] = (arr[i] * k + (stack.Count > 0 ? dp[stack.Peek()] : 0)) % MOD;
result = (result + dp[i]) % MOD;
stack.Push(i);
}
return (int)result;
}
}Through dynamic programming, this Python solution consolidates subarray results iteratively, using an array dp to track cumulative outcomes efficiently.
Time Complexity: O(n)
Space Complexity: O(n) owing to dp and stack storage.
Approach 3: Monotonic Stack
The problem asks for the sum of the minimum values of each subarray, which is equivalent to finding the number of subarrays for which each element arr[i] is the minimum, then multiplying by arr[i], and finally summing these up.
Therefore, the focus of the problem is to find the number of subarrays for which arr[i] is the minimum. For arr[i], we find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i).
Note, why do we find the first position right[i] to the right that is less than or equal to arr[i], rather than less than arr[i]? This is because if we find the first position right[i] to the right that is less than arr[i], it will lead to duplicate calculations.
Let's take an example to illustrate. For the following array:
The element at index 3 is 2, the first element to its left that is less than 2 is at index 0. If we find the first element to its right that is less than 2, we get index 7. That is, the subarray interval is (0, 7). Note that this is an open interval.
0 4 3 2 5 3 2 1
* ^ *
In the same way, we can find the subarray interval for the element at index 6, and find that its subarray interval is also (0, 7). That is, the subarray intervals for the elements at index 3 and index 6 are the same. This leads to duplicate calculations.
0 4 3 2 5 3 2 1
* ^ *
If we find the first element to its right that is less than or equal to its value, there will be no duplication, because the subarray interval for the element at index 3 becomes (0, 6), and the subarray interval for the element at index 6 is (0, 7), which are not the same.
Back to this problem, we just need to traverse the array, for each element arr[i], use a monotonic stack to find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i), then multiply by arr[i], and finally sum these up.
Be aware of data overflow and modulo operations.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array arr.
function sumSubarrayMins(arr: number[]): number {
const n: number = arr.length;
const left: number[] = Array(n).fill(-1);
const right: number[] = Array(n).fill(n);
const stk: number[] = [];
for (let i = 0; i < n; ++i) {
while (stk.length > 0 && arr[stk.at(-1)] >= arr[i]) {
stk.pop();
}
if (stk.length > 0) {
left[i] = stk.at(-1);
}
stk.push(i);
}
stk.length = 0;
for (let i = n - 1; ~i; --i) {
while (stk.length > 0 && arr[stk.at(-1)] > arr[i]) {
stk.pop();
}
if (stk.length > 0) {
right[i] = stk.at(-1);
}
stk.push(i);
}
const mod: number = 1e9 + 7;
let ans: number = 0;
for (let i = 0; i < n; ++i) {
ans += ((((i - left[i]) * (right[i] - i)) % mod) * arr[i]) % mod;
ans %= mod;
}
return ans;
}func sumSubarrayMins(arr []int) (ans int) {
n := len(arr)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
}
stk := []int{}
for i, v := range arr {
for len(stk) > 0 && arr[stk[len(stk)-1]] >= v {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && arr[stk[len(stk)-1]] > arr[i] {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
const mod int = 1e9 + 7
for i, v := range arr {
ans += (i - left[i]) * (right[i] - i) * v % mod
ans %= mod
}
return
}use std::collections::VecDeque;
impl Solution {
pub fn sum_subarray_mins(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut left = vec![-1; n];
let mut right = vec![n as i32; n];
let mut stk: VecDeque<usize> = VecDeque::new();
for i in 0..n {
while !stk.is_empty() && arr[*stk.back().unwrap()] >= arr[i] {
stk.pop_back();
}
if let Some(&top) = stk.back() {
left[i] = top as i32;
}
stk.push_back(i);
}
stk.clear();
for i in (0..n).rev() {
while !stk.is_empty() && arr[*stk.back().unwrap()] > arr[i] {
stk.pop_back();
}
if let Some(&top) = stk.back() {
right[i] = top as i32;
}
stk.push_back(i);
}
let MOD = 1_000_000_007;
let mut ans: i64 = 0;
for i in 0..n {
ans += ((((right[i] - (i as i32)) * ((i as i32) - left[i])) as i64) * (arr[i] as i64))
% MOD;
ans %= MOD;
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n), where n is the array size. |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Previous Less Element | O(n) | O(n) | When explaining the incremental contribution idea or building intuition with DP relations. |
| Monotonic Stack Contribution Counting | O(n) | O(n) | Best general solution. Handles large inputs efficiently and is the expected interview approach. |
Frequently asked questions
Is Sum of Subarray Minimums easy or hard?
Sum of Subarray Minimums is rated Medium on LeetCode but feels challenging if you have not practiced monotonic stack problems. Once you recognize the pattern of counting element contributions using nearest smaller elements, the implementation becomes straightforward.
Sum of Subarray Minimums Python/Java solution
Python and Java implementations typically use a stack to track indices of increasing elements. While iterating through the array, elements are popped when a smaller value appears, allowing calculation of contribution ranges. The same logic works across Python, Java, C++, and JavaScript with O(n) complexity.
How to solve Sum of Subarray Minimums in O(n)?
Use a monotonic increasing stack to find the previous and next smaller elements for every index. These boundaries determine the number of subarrays where the element is the minimum. Multiply the left span, right span, and the element value to compute its contribution, then sum all contributions modulo 1e9+7.
What is the best approach for Sum of Subarray Minimums?
The best approach uses a monotonic increasing stack to determine how many subarrays treat each element as the minimum. For every index, calculate the distance to the previous smaller element and the next smaller element. Multiply these counts to determine how many subarrays include that value as the minimum. This algorithm runs in O(n) time with O(n) space.
Is Sum of Subarray Minimums asked at Google/Amazon/Meta?
Sum of Subarray Minimums appears frequently in interviews at companies that test advanced array and stack patterns, including Amazon, Google, and Meta. It evaluates knowledge of monotonic stacks, contribution counting, and efficient range analysis.
What data structure is used in Sum of Subarray Minimums?
The primary data structure is a monotonic stack that maintains indices in increasing order of values. This structure helps efficiently compute nearest smaller elements on the left and right in linear time.
What is the time complexity of Sum of Subarray Minimums?
The optimal solution runs in O(n) time because each array index is pushed to and popped from the stack at most once. Space complexity is O(n) due to the stack and auxiliary arrays used to track previous or next smaller elements.