LeetCode #2104 Medium

Sum of Subarray Ranges

The range of a subarray is its maximum minus its minimum. Return the sum of ranges over all subarrays.

monotonic-stackarraycontribution

02

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.

03

Approach

1

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.

2

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).

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def subArrayRanges(self, nums):
▶3        n = len(nums)
▶4 
▶5        def total(is_min):
▶6            prev, nxt = [-1] * n, [n] * n
▶7            st = []
▶8            for i in range(n):
▶9                while st and ((nums[st[-1]] >= nums[i]) if is_min else (nums[st[-1]] <= nums[i])):
▶10                    st.pop()
▶11                prev[i] = st[-1] if st else -1
▶12                st.append(i)
▶13            st = []
▶14            for i in range(n - 1, -1, -1):
▶15                while st and ((nums[st[-1]] > nums[i]) if is_min else (nums[st[-1]] < nums[i])):
▶16                    st.pop()
▶17                nxt[i] = st[-1] if st else n
▶18                st.append(i)
▶19            return sum(nums[i] * (i - prev[i]) * (nxt[i] - i) for i in range(n))
▶20 
▶21        return total(False) - total(True)

05

Edge cases

All elements equal

Max equals min in every subarray, so the answer is 0 — the sharpest test of correct tie handling.

Single element

Its range is 0, so the answer is 0.

Sorted array

Maxima and minima are at opposite ends of every subarray; the formula still applies unchanged.

Negative values

No special handling needed — no modulus is applied in this problem, unlike Sum of Subarray Minimums.

06

Complexity

Time

O(n)

Space

O(n)

Four monotonic-stack passes. The O(n^2) double loop also passes but teaches less.