Total of Every Subarray's Minimum Value
Solve this Problemarr, find the sum of the minimum values of every contiguous subarray.
Enumerating every subarray directly works but wastes effort — a smarter approach flips the question: instead of "what's the minimum of this subarray?", ask "in how many subarrays is this element the minimum?" for each element individually. An element is the minimum of exactly the subarrays that start somewhere between its nearest strictly-smaller neighbor to the left and itself, and end somewhere between itself and its nearest smaller-or-equal neighbor to the right — both boundaries found in a single monotonic-stack pass each. Multiplying each element's value by how many such subarrays it dominates, and summing across every element, reaches the same total in O(n) instead of O(n²).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arr.length ≤ 12 - ◆
1 ≤ arr[i] ≤ 100 - ◆
The answer fits comfortably in a 32-bit signed integer for this input size
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Track the Running Minimum for Every Start
BruteFor every starting index i, extend the subarray one element at a time toward the end, keeping a running minimum as it grows — every extension adds exactly one new subarray, and its minimum is always just min(previous running minimum, the newly included element). Add each subarray's minimum into the total as it's computed. This avoids re-scanning each subarray from scratch, but still visits every one of the O(n²) subarrays individually.
O(n²)O(1)1class Solution {
2 public int sumSubarrayMinimums(int[] arr) {
3 int n = arr.length;
4 long sum = 0;
5 for (int i = 0; i < n; i++) {
6 int mn = arr[i];
7 for (int j = i; j < n; j++) {
8 mn = Math.min(mn, arr[j]);
9 sum += mn;
10 }
11 }
12 return (int) sum;
13 }
14}Optimal — Count Each Element's Contribution With Two Monotonic Stacks
OptimalInstead of visiting every subarray, ask a different question for each element: in how many subarrays is this element the minimum? An element at index i is the minimum of exactly those subarrays that start somewhere between its nearest strictly-smaller element to the left (exclusive) and i, and end somewhere between i and its nearest smaller-or-equal element to the right (exclusive) — using "smaller-or-equal" on one side only, to avoid double counting when duplicate values exist. Both boundaries are found with a monotonic stack, one pass in each direction. Each element's total contribution is then value × (choices on the left) × (choices on the right), summed once per element.
O(n)O(n)1class Solution {
2 public int sumSubarrayMinimums(int[] arr) {
3 int n = arr.length;
4 int[] prevLess = new int[n];
5 int[] nextLessEq = new int[n];
6 Deque<Integer> stack = new ArrayDeque<>();
7 for (int i = 0; i < n; i++) {
8 while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
9 prevLess[i] = stack.isEmpty() ? -1 : stack.peek();
10 stack.push(i);
11 }
12 stack.clear();
13 for (int i = n - 1; i >= 0; i--) {
14 while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
15 nextLessEq[i] = stack.isEmpty() ? n : stack.peek();
16 stack.push(i);
17 }
18 long sum = 0;
19 for (int i = 0; i < n; i++) {
20 long left = i - prevLess[i];
21 long right = nextLessEq[i] - i;
22 sum += (long) arr[i] * left * right;
23 }
24 return (int) sum;
25 }
26}