AlgoMaster Logo

Sum of Subarray Minimums

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to consider every contiguous subarray of arr, find the minimum element in each, and sum all those minimums. Enumerating all subarrays involves O(n^2) subarrays, and finding the minimum of each from scratch adds another O(n) factor, for O(n^3) overall. That is too slow.

A better perspective is to flip the question. Instead of asking "what is the minimum of each subarray?", ask "for each element, how many subarrays is it the minimum of?" Multiply each element by that count and sum the products. This turns a subarray enumeration problem into a contribution counting problem, which monotonic stacks solve in linear time.

Key Constraints:

  • 1 <= arr.length <= 3 * 10^4 -- With n up to 30,000, an O(n^2) solution does roughly 450 million operations. That is borderline within typical time limits, so a linear solution is the safer target.
  • 1 <= arr[i] <= 3 * 10^4 -- All values are positive integers, with no zeros or negatives.
  • The answer must be returned modulo 10^9 + 7 -- The unmodded sum can exceed a 64-bit integer (up to about 3 10^4 values times 4.5 10^8 subarrays), so reduce modulo 10^9 + 7 as you accumulate, and use a 64-bit type for the products.

Approach 1: Brute Force

Intuition

Enumerate every subarray, track the running minimum as we extend, and add it to the sum. For each starting index i, extend j from i to n-1, updating the minimum at each step. Carrying the minimum forward avoids recomputing it from scratch, giving O(n^2) instead of O(n^3).

Algorithm

  1. Initialize result = 0 and set MOD = 10^9 + 7.
  2. For each starting index i from 0 to n-1:
    • Set currentMin = arr[i].
    • For each ending index j from i to n-1:
      • Update currentMin = min(currentMin, arr[j]).
      • Add currentMin to result (modulo MOD).
  3. Return result.

Visualization and Code

Loading animation...

This rediscovers each element's contribution independently for every starting index. The next approach computes how many subarrays each element is the minimum of without enumerating them.

Approach 2: Monotonic Stack (Contribution Counting)

Intuition

Instead of iterating over subarrays and finding their minimums, iterate over elements and count how many subarrays each one is the minimum of. The answer is then the sum of arr[i] * count[i] over all i.

The reach of arr[i] as a minimum is bounded by the nearest smaller element on each side. If the nearest smaller element to the left of i is at index left and the nearest smaller element to the right is at index right, then arr[i] is the minimum of every subarray that starts anywhere in (left, i] and ends anywhere in [i, right). The count of such subarrays is (i - left) * (right - i): the number of valid left endpoints times the number of valid right endpoints.

A monotonic stack finds the previous-smaller and next-smaller boundaries for every index in O(n) total.

Duplicates need care. If two equal elements both treated their boundary as "strictly smaller" on both sides, a subarray whose minimum appears twice would be counted twice. The fix is asymmetric comparisons: take the previous strictly smaller element on the left and the next smaller-or-equal element on the right. Each subarray's minimum is then attributed to exactly one index.

Algorithm

  1. Create two arrays of boundary indices: prevLess[i] holds the index of the previous strictly smaller element (or -1 if none exists), and nextLess[i] holds the index of the next smaller-or-equal element (or n if none exists).
  2. Use a monotonic increasing stack to compute prevLess[]:
    • Scan left to right. For each element, pop all elements from the stack that are greater than or equal to arr[i].
    • If the stack is empty, prevLess[i] = -1. Otherwise, prevLess[i] = stack.peek().
    • Push i onto the stack.
  3. Use a monotonic increasing stack to compute nextLess[]:
    • Scan right to left. For each element, pop all elements that are strictly greater than arr[i].
    • If the stack is empty, nextLess[i] = n. Otherwise, nextLess[i] = stack.peek().
    • Push i onto the stack.
  4. Compute the answer: for each i, the endpoint counts are left = i - prevLess[i] and right = nextLess[i] - i; sum arr[i] * left * right over all i, modulo 10^9 + 7.

Visualization and Code

Loading animation...

This approach uses three passes and two auxiliary arrays. The next approach folds the boundary lookup and the summation into a single left-to-right pass with a DP recurrence.

Approach 3: Single-Pass Monotonic Stack with DP

Intuition

A single left-to-right pass can do the work by combining the monotonic stack with a running accumulator. Define dp[i] as the sum of minimums of all subarrays ending at index i. The final answer is dp[0] + dp[1] + ... + dp[n-1].

To compute dp[i], find the previous strictly smaller element at index j (or j = -1 if none exists). Every subarray ending at i that starts at positions j+1 through i has arr[i] as its minimum, since arr[i] is smaller than every element after j up to i. There are i - j such subarrays, contributing arr[i] * (i - j). Every subarray that starts at or before j has its minimum to the left of i, with the same value it had for a subarray ending at j, which is exactly dp[j]. So:

dp[i] = dp[j] + arr[i] * (i - j), with dp[j] dropped when j = -1.

Algorithm

  1. Initialize a stack and an array dp where dp[i] represents the sum of minimums of all subarrays ending at index i.
  2. For each index i from 0 to n-1:
    • Pop all stack elements where arr[stack.top()] >= arr[i].
    • If the stack is empty, dp[i] = arr[i] * (i + 1) (arr[i] is the minimum of all subarrays ending at i).
    • Otherwise, let j = stack.top(). Then dp[i] = dp[j] + arr[i] * (i - j).
    • Push i onto the stack.
    • Add dp[i] to the running result.
  3. Return result % MOD.

Visualization and Code

Loading animation...