Sum of Subarray Ranges
The range of a subarray is its maximum minus its minimum. Return the sum of ranges over all subarrays.
Open on LeetCode ↗Intuition
It is easy to write the max pass and the min pass with different tie-breaking rules — say, strict on both sides for max but strict-one-side for min — because each pass looks correct in isolation. But sum(max) - sum(min) is only valid if a tied run of equal values gets partitioned the same way in both passes; otherwise the subtraction does not cancel and the answer is off on any input with duplicates. Sums distribute over subtraction, so the sum of (max - min) equals the sum of all maxima minus the sum of all minima, but only once both passes use one shared, consistent tie convention.
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
Split the sum
Because summation is linear, sum(max_i - min_i) = sum(max_i) - sum(min_i). Neither half needs to know anything about the other, so one hard-looking problem becomes two copies of a solved one.
Sum of minima by contribution
For each element, count the subarrays where it is the minimum using previous-smaller and next-smaller boundaries: (i - pse) * (nse - i). Multiply by the value and sum. Monotonic stacks give both boundary arrays in O(n).
Sum of maxima, and the tie rule
Flip every comparison — previous greater and next greater — and repeat, but flip it as a mirror image, not independently: if minima use strictly-smaller-previous and smaller-or-equal-next, maxima must use strictly-greater-previous and greater-or-equal-next. Mixing conventions between the two passes is the actual bug that breaks this problem — each pass alone still returns a plausible-looking number, and only the final subtraction is wrong. Four stack passes total, so O(n) time and O(n) space. The problem allows an O(n^2) solution, but the contribution version is the one worth knowing.
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.