Sum of Subarray Ranges
The range of a subarray is its maximum minus its minimum. Return the sum of ranges over all subarrays.
- 1 <= nums.length <= 1000
- -10⁹ <= nums[i] <= 10⁹
Intuition
Sum of subarray ranges sums the difference between the maximum and minimum of every subarray. The brute force over all O(n²) subarrays is acceptable for small inputs, but the linear solution is the point.
The key observation splits the problem in two:
- The sum of all ranges equals the sum of all subarray maximums minus the sum of all subarray minimums, because each range is a difference and summation distributes over subtraction.
So this becomes two independent instances of Sum of Subarray Minimums — one computing minimums, one computing maximums with the comparison reversed.
Each half uses the same technique: for every element, count how many subarrays it is the extreme of, then weight by its value. The boundaries are the nearest smaller elements on each side for minimums, and the nearest larger elements for maximums.
With left and right as the distances to those boundaries, the element contributes to left × right subarrays.
The duplicate-handling rule carries over unchanged. Use a strict comparison on one side and non-strict on the other, in both passes, so subarrays with tied extremes are attributed to exactly one element.
A monotonic increasing stack serves the minimums and a decreasing stack the maximums — the same code with the comparison flipped.
Unlike Sum of Subarray Minimums, no modulus is required here, since the constraints keep the result within range. Applying one anyway produces wrong answers, which is an easy habit to carry over incorrectly.
Four stack passes, or two if each computes both boundaries, give O(n) time and O(n) space.
Range is max minus min, and summation is linear — so the total equals (sum of all subarray maxima) minus (sum of all subarray minima). Each half is the contribution-counting technique from Sum of Subarray Minimums, run with the comparisons flipped.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Split into two sums
The total equals the sum of all subarray maximums minus the sum of all minimums, since summation distributes over the subtraction in each range.
Reuse the minimums technique
Each half is Sum of Subarray Minimums — count how many subarrays each element is the extreme of, then weight by its value.
Flip the comparison for maximums
Minimums use nearest smaller elements as boundaries; maximums use nearest larger ones. The same code with the comparison reversed.
Multiply the distances
An element is the extreme of left × right subarrays, where those are the distances to its two boundaries.
Break ties asymmetrically in both passes
Strict on one side, non-strict on the other, in both the minimum and maximum passes — otherwise tied extremes are counted twice.
Apply no modulus
The constraints keep the result in range here, unlike Sum of Subarray Minimums. Applying a modulus out of habit produces wrong answers.
Cost of the approach
Each element is pushed and popped a constant number of times, giving O(n) time and O(n) space.
Solution & live demo
Common pitfalls
Trying to compute ranges directly
for each subarray: total += max(sub) - min(sub)
return total(False) - total(True)
There's no monotonic stack for "range" itself. Splitting by linearity gives two problems that each have a known linear solution, then subtracting recombines them exactly.
Reusing the same comparison operators for max
while st and nums[st[-1]] >= nums[i]: # for both
(nums[st[-1]] >= nums[i]) if is_min else (nums[st[-1]] <= nums[i])
The maxima pass needs previous-greater and next-greater spans, which means inverted comparisons. Sharing the minima operators computes the minima sum twice and returns zero.
Getting the subtraction order backwards
return total(True) - total(False)
return total(False) - total(True)
Range is max − min, so the maxima sum leads. Reversing gives a negative of the correct answer — obviously wrong on inspection, but easy to write when the flag's meaning isn't fresh.
Edge cases
Max equals min in every subarray, so the answer is 0 — the sharpest test of correct tie handling.
Its range is 0, so the answer is 0.
Maxima and minima are at opposite ends of every subarray; the formula still applies unchanged.
No special handling needed — no modulus is applied in this problem, unlike Sum of Subarray Minimums.