The challenge
Sum the minimum of every nonempty contiguous subarray, modulo 1,000,000,007.
Positive integer values up to 30,000; length ≤ 30,000. Empty input returns 0.
Example
[3,1,2,4] → 17.
Use the walkthrough below to inspect the input and each state change.
See Sum of Subarray Minimums, step by step
Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.
Zero-based input · top labeled explicitlyLIFO
- Current input index
- —
- Main stack size
- 0
Step 01 / 10
Start with an empty stack
Read the input in order. The stack keeps only the state needed to resolve the next item.
Answer so far
Not recorded yet
- Main stack · bottom → top
- Empty
- Auxiliary stack · bottom → top
- Empty
View exact input and state
Input: [3,1,2,4]
Main stack: []. Auxiliary stack · bottom → top: [].
Put it into code
Use previous strictly smaller and next smaller-or-equal boundaries.
Indices are zero-based. C++ uses C++17 or later.
def solve(values):
mod = 1_000_000_007
stack, total = [], 0
n = len(values)
for right in range(n + 1):
# Previous strictly smaller, next smaller-or-equal.
while stack and (right == n or values[stack[-1]] >= values[right]):
i = stack.pop()
left = stack[-1] if stack else -1
total = (total + values[i] * (i - left) * (right - i)) % mod
if right < n: stack.append(right)
return total
#include <algorithm>
#include <optional>
#include <utility>
#include <string>
#include <vector>
using namespace std;
int solve(const vector<int>& values) {
const long long mod = 1000000007;
vector<int> stack;
long long total = 0;
int n = static_cast<int>(values.size());
for (int right = 0; right <= n; ++right) {
// Previous strictly smaller, next smaller-or-equal.
while (!stack.empty() && (right == n || values[stack.back()] >= values[right])) {
int i = stack.back(); stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
total = (total + 1LL * values[i] * (i - left) * (right - i)) % mod;
}
if (right < n) stack.push_back(right);
}
return static_cast<int>(total);
}