Command Palette

Search for a command to run...

Hectal
Problem 42.3 · Pattern Recognition DrillsMedium

Sum of Subarray Minimums

What it teaches:

Practise it on judges as “Sum of Subarray Minimums”.

In plain words

Instead of looking at every stretch of numbers and finding its smallest, turn it around: for each number, ask how many stretches it is the smallest of. That is (how far it can reach left before meeting something smaller) × (how far it can reach right before meeting something smaller or equal). Multiply that count by the number and add up.

Return the sum of the minimums of all subarrays, modulo 10⁹ + 7. Example: arr = [3, 1, 2, 4] → 17.

The problem

Return the sum of min(subarray) over all contiguous subarrays, modulo 10⁹ + 7.

Example 1

Input: arr = [3, 1, 2, 4]
Output: 17

Constraints

  • 1 ≤ n ≤ 3 × 10⁴

Pattern clues in the wording

  • → Sum over all subarrays of a min/max
  • → Previous / next smaller element

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
arr = [3,1,2,4]
17
2
arr = [11,81,94,43,3]
444

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Contribution with monotonic stacks · O(n)
1

Contribution with monotonic stacks

Time O(n) Space O(n)

left[i] = distance to the previous smaller element; right[i] = distance to the next smaller-or-equal. Sum arr[i] × left × right.

▶ Dry run: Each number's share of the totalarr = [3, 1, 2, 4]
3
0
1
1
2
2
4
3

left reach(list)

1211

Step 1/4Left pass: 3 reaches 1 cell (itself). 1 pops the bigger 3, reaching 2 cells. 2 and 4 stop at a smaller neighbour: 1 each.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] left = new int[n], right = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
            left[i] = st.isEmpty() ? i + 1 : i - st.peek();
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
            right[i] = st.isEmpty() ? n - i : st.peek() - i;
            st.push(i);
        }
        long total = 0, MOD = 1_000_000_007L;
        for (int i = 0; i < n; i++) total = (total + (long) arr[i] * left[i] * right[i]) % MOD;
        return (int) total;
    }
}

Verdict: Turns O(n²) subarrays into n contributions.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Equal values
  • Strictly increasing array

Mistakes people make

  • Using ≥ (or >) on both sides: duplicates are counted twice or not at all.

Interview

Follow-up questions

How do you get the sum of subarray ranges (max − min)?