Sum of subarray minimums

Array Dynamic Programming Stack Monotonic Stack

38.3% acceptance

Feb 25, 2026

9156

732

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_subarray_mins(arr: Vec<i32>) -> i32 {
    let md = 1_000_000_007i64;
    let n = arr.len();
    let mut stack: Vec<usize> = Vec::new();
    let mut left = vec![0usize; n];
    let mut right = vec![0usize; n];
    for i in 0..n {
      while stack.last().map_or(false, |&j| arr[j] >= arr[i]) { stack.pop(); }
      left[i] = match stack.last() { Some(&j) => i - j, None => i + 1 };
      stack.push(i);
    }
    stack.clear();
    for i in (0..n).rev() {
      while stack.last().map_or(false, |&j| arr[j] > arr[i]) { stack.pop(); }
      right[i] = match stack.last() { Some(&j) => j - i, None => n - i };
      stack.push(i);
    }
    let mut ans = 0i64;
    for i in 0..n { ans = (ans + arr[i] as i64 * left[i] as i64 * right[i] as i64) % md; }
    ans as i32
  }
}