Sum of Subarray Ranges
Add up the range (largest minus smallest) of every subarray in linear time, as the sum of subarray maximums minus the sum of subarray minimums.
Problem Understanding
Sum of Subarray Ranges: the range of a subarray is its largest element minus its smallest. Given nums, return the sum of the ranges of all subarrays.
Examples: [1,2,3] → 4; [1,3,3] → 4; [4,-2,-3,4,1] → 59.
The Intuition: Two Contribution Counts
Range = max − min, so:
- Sum of all subarray maximums: every value counts as the maximum of the subarrays between its nearest larger neighbors.
- Sum of all subarray minimums: the same with nearest smaller neighbors, which is Sum of Subarray Minimums.
- Subtract.
Both counts come from a monotonic stack pass, popping on <= for maximums and >= for minimums so ties are counted once.
Interactive Walkthrough
TINTED = WHERE THE POPPED VALUE IS THE MAX (PASS 1) OR MIN (PASS 2)
MAX SUM − MIN SUM
pass 1: maximums
0
1
2
stack (bottom → top): value, index below
EMPTY
subarrays
:
added
:
pass total
0
Sum of ranges = (sum of every subarray maximum) − (sum of every subarray minimum)
Next
Pass 1: sum of maximums. The stack keeps decreasing values
nums
Two passes run: maximums, then minimums. On each pop the stretch where the popped value is the extreme is tinted and its contribution added. Try Example 3 to see negative values.
Dry Run Table
Input: [1,2,3], whose subarrays are [1], [2], [3], [1,2], [2,3], [1,2,3].
| Values | Sum | |
|---|---|---|
| Maximums | 1, 2, 3, 2, 3, 3 | 14 |
| Minimums | 1, 2, 3, 1, 2, 1 | 10 |
Answer: 14 − 10 = 4.
The Solution Template
One helper, called with each comparison.
Sum of Subarray Ranges Code
1var subArrayRanges = function(nums) {2 const n = nums.length;3 const total = (beats) => {4 const stack = [];5 let s = 0;6 for (let i = 0; i <= n; i++) {7 while (stack.length && (i === n || beats(nums[stack[stack.length - 1]], nums[i]))) {8 const mid = stack.pop();9 const left = stack.length ? stack[stack.length - 1] : -1;10 s += nums[mid] * (mid - left) * (i - mid);11 }12 stack.push(i);13 }14 return s;15 };16 return total((top, x) => top <= x) - total((top, x) => top >= x);17};
Edge Cases & Common Mistakes
- Ties: pop on
<=(max) or>=(min) and stop at strict on the other side, or equal values are double counted. - One element: its range is 0.
- Negative values: the formula works unchanged.
- Overflow: use 64-bit sums.
- Forgetting the flush: values left on the stack must be counted with right = n.
Summary
Compute the sum of subarray maximums and of subarray minimums with two monotonic-stack passes, and subtract. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet