Sum of Subarray Minimums

Medium
383.

Sum of Subarray Minimums

Sum of Subarray Minimums is a medium coding problem on arrays, dynamic programming and stack, asked in Amazon, Google, Bloomberg and Sprinklr interviews.

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 <= 100
  • 1 <= 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?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 100
  • 1 <= 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

  1. Hint 1

    Instead of enumerating subarrays, ask how many subarrays each element is the minimum of.

  2. Hint 2

    For index i, let left[i] be the number of choices for the subarray's start and right[i] the choices for its end; the contribution is arr[i] * left[i] * right[i].

  3. 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

  1. Left pass: pop while arr[top] > arr[i]; left[i] = i - top (or i + 1).
  2. Right pass: pop while arr[top] >= arr[i]; right[i] = top - i (or n - i).
  3. Sum arr[i] · left[i] · right[i] modulo 10⁹ + 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 total

Java

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