The sum of the minimum of every subarray
Medium · Target 20 minutes · Stack· Type asked at
IMC
Two Sigma
Barclays
You're given an array of positive integers arr. Take the minimum of every contiguous
subarray and add them all up, and return the total modulo 10⁹ + 7.
Examples
| Input | Output | Why |
|---|---|---|
arr = [3, 1, 2, 4] | 17 | If you write out the ten subarrays their minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1 and 1, which come to 17. |
arr = [11, 81, 94, 43, 3] | 444 | |
arr = [2, 2, 2] | 12 | All six subarrays have 2 as their minimum so it's 12, and this is the one I'd use to check that ties don't get counted twice. |
Constraints
- 1 ≤ n ≤ 3 × 10⁴
- 1 ≤ arr[i] ≤ 3 × 10⁴
Hints
Hint 1
Going over every subarray is O(n²) at best. What if you asked, for each arr[i], how many subarrays it's the minimum of?
Hint 2
arr[i] is the minimum of a subarray as long as the subarray doesn't reach past the nearest smaller value on either side. So you need those two boundaries for every i.
Hint 3
A monotonic stack finds the previous smaller and the next smaller in one pass each. Then arr[i] counts (i − left) × (right − i) times. To stop equal values being counted twice, use strictly smaller on one side and smaller-or-equal on the other.
Where people lose marks
- Using strictly smaller on both sides, which I've seen a fair bit. It counts a subarray like [2, 2] twice, so one of the two sides has to take the equal values.
- Leaving the modulo until the very end, when the total can get to about 3 × 10⁴ × 4.5 × 10⁸ and that's well past 32 bits. You'd take it as you go or use 64-bit sums.
- Getting the missing boundaries wrong. If there's no smaller value on the left you'd want left = −1, and if there's none on the right it's right = n.
Dry run on [3,1,2,4]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5arr30112243left-10-111223right10414243
I'd find, for each value, the previous smaller index on the left and the next smaller-or-equal on the right with two stack passes.
-
Step 2 / 5arr30112243left-10-111223right10414243total3
3 is the minimum of (0 − (-1)) × (1 − 0) = 1 subarray, so it puts in 3 × 1 = 3 and you're at 3.
-
Step 3 / 5arr30112243left-10-111223right10414243total9
1 is the minimum of (1 − (-1)) × (4 − 1) = 6 subarrays, which adds 6 and brings the total to 9.
-
Step 4 / 5arr30112243left-10-111223right10414243total13
2 is the minimum of (2 − (1)) × (4 − 2) = 2 subarrays, so it puts in 2 × 2 = 4 and you're at 13.
-
Step 5 / 5arr30112243left-10-111223right10414243total17
4 is the minimum of (3 − (2)) × (4 − 3) = 1 subarray, which adds 4 and brings the total to 17.
How to think about it
Adding up the minimum of every subarray directly is O(n²) even if you're clever about keeping a running
minimum. I'd turn it round and ask how many subarrays each arr[i] is the minimum of. That's the subarrays
that contain i and don't reach as far as a smaller value on either side.
So for each i you want left, the index of the previous value that's smaller, and
right, the index of the next one. A subarray with i as its minimum can start anywhere in
left + 1 .. i and end anywhere in i .. right − 1, which makes
(i − left) × (right − i) of them, and arr[i] adds that many times itself to the total.
Both boundaries come from a monotonic stack in one pass. The catch is equal values. If you use strictly smaller on both sides, a subarray of equal minimums gets counted once for each of them, so I'd use strictly smaller on the left and smaller-or-equal on the right. Then a subarray with several equal minimums only gets counted for the rightmost of them, since the others can't reach past it.
Complexity. Time O(n) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def sum_subarray_mins(arr):
MOD = 10**9 + 7
n = len(arr)
left, right, st = [-1] * n, [n] * n, []
for i in range(n): # previous strictly smaller
while st and arr[st[-1]] >= arr[i]:
st.pop()
left[i] = st[-1] if st else -1
st.append(i)
st = []
for i in range(n - 1, -1, -1): # next smaller or equal
while st and arr[st[-1]] > arr[i]:
st.pop()
right[i] = st[-1] if st else n
st.append(i)
return sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) % MOD#include <vector>
long long solve(const std::vector<int>& arr) {
const long long MOD = 1000000007;
int n = (int)arr.size();
std::vector<int> left(n), right(n), st;
for (int i = 0; i < n; ++i) { // previous strictly smaller
while (!st.empty() && arr[st.back()] >= arr[i]) st.pop_back();
left[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; --i) { // next smaller or equal
while (!st.empty() && arr[st.back()] > arr[i]) st.pop_back();
right[i] = st.empty() ? n : st.back();
st.push_back(i);
}
long long total = 0;
for (int i = 0; i < n; ++i) total = (total + (long long)arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
return total;
}class Solution {
public int sumSubarrayMins(int[] arr) {
final long MOD = 1_000_000_007L;
int n = arr.length, top = -1;
int[] left = new int[n], right = new int[n], st = new int[n];
for (int i = 0; i < n; i++) { // previous strictly smaller
while (top >= 0 && arr[st[top]] >= arr[i]) top--;
left[i] = top >= 0 ? st[top] : -1;
st[++top] = i;
}
top = -1;
for (int i = n - 1; i >= 0; i--) { // next smaller or equal
while (top >= 0 && arr[st[top]] > arr[i]) top--;
right[i] = top >= 0 ? st[top] : n;
st[++top] = i;
}
long total = 0;
for (int i = 0; i < n; i++) total = (total + (long) arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
return (int) total;
}
}function sumSubarrayMins(arr) {
const MOD = 1000000007n, n = arr.length, left = new Array(n), right = new Array(n);
let st = [];
for (let i = 0; i < n; i++) { // previous strictly smaller
while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();
left[i] = st.length ? st[st.length - 1] : -1;
st.push(i);
}
st = [];
for (let i = n - 1; i >= 0; i--) { // next smaller or equal
while (st.length && arr[st[st.length - 1]] > arr[i]) st.pop();
right[i] = st.length ? st[st.length - 1] : n;
st.push(i);
}
let total = 0n;
for (let i = 0; i < n; i++) total += BigInt(arr[i]) * BigInt(i - left[i]) * BigInt(right[i] - i);
return Number(total % MOD);
}fn solve(arr: &[i64]) -> i64 {
const MOD: i64 = 1_000_000_007;
let n = arr.len();
let (mut left, mut right) = (vec![-1i64; n], vec![n as i64; n]);
let mut st: Vec<usize> = Vec::new();
for i in 0..n { // previous strictly smaller
while let Some(&t) = st.last() { if arr[t] >= arr[i] { st.pop(); } else { break; } }
if let Some(&t) = st.last() { left[i] = t as i64; }
st.push(i);
}
st.clear();
for i in (0..n).rev() { // next smaller or equal
while let Some(&t) = st.last() { if arr[t] > arr[i] { st.pop(); } else { break; } }
if let Some(&t) = st.last() { right[i] = t as i64; }
st.push(i);
}
let mut total = 0i64;
for i in 0..n { total = (total + arr[i] * (i as i64 - left[i]) % MOD * (right[i] - i as i64)) % MOD; }
total
}-- Stacks hold (index, value), top at the head.
solve :: [Int] -> Int
solve arr = sum (zipWith3 (\(i, x) l r -> x * (i - l) * (r - i)) ixs lefts rights) `mod` 1000000007
where
n = length arr
ixs = zip [0 ..] arr
-- previous strictly smaller
lefts = go [] ixs
where go _ [] = []
go st ((i, x) : rest) =
let st' = dropWhile (\(_, y) -> y >= x) st
in (case st' of { ((j, _) : _) -> j; [] -> -1 }) : go ((i, x) : st') rest
-- next smaller or equal, from the right
rights = reverse (go [] (reverse ixs))
where go _ [] = []
go st ((i, x) : rest) =
let st' = dropWhile (\(_, y) -> y > x) st
in (case st' of { ((j, _) : _) -> j; [] -> n }) : go ((i, x) : st') restVariants to try
- The sum of subarray maximums is the same with the comparisons flipped, and the sum of (max − min) over every subarray is the difference of the two.
- If the subarrays have to be at least k long, the count for each i needs a little more arithmetic but the stacks don't change.
Next problems
Days until a warmer day
For each day, how long until it is warmer? Days wait on a stack until a warmer one arrives and settles them.
Open the problem → Medium15 minHow many days in a row the price was no higher
For each day, count back over the run of days whose price was at most today's. A stack of the days still waiting for a higher price gets it in one pass.
Open the problem → Hard25 minLargest rectangle in a bar chart
Each bar is the height of some rectangle. A stack finds, for every bar at once, how far it can stretch.
Open the problem →Write a solution and run it against the real test table.
Keep going
Days until a warmer day
For each day, how long until it is warmer? Days wait on a stack until a warmer one arrives and settles them.
Open the problem → Medium15 minHow many days in a row the price was no higher
For each day, count back over the run of days whose price was at most today's. A stack of the days still waiting for a higher price gets it in one pass.
Open the problem → Hard25 minLargest rectangle in a bar chart
Each bar is the height of some rectangle. A stack finds, for every bar at once, how far it can stretch.
Open the problem → StackThe pattern behind it
Keep the elements whose question is still open; each new element settles the ones it beats and waits its turn.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.