Sum of Subarray Ranges

1. Reframe the Problem

• Instead of computing each subarray's range individually, observe that:
• Sum of ranges = Sum of subarray maximums − Sum of subarray minimums.
• This separates the problem into two independent monotonic stack problems.

2. Compute Sum of Subarray Maximums

• For each element nums[i], determine how many subarrays have nums[i] as their maximum.
• Use a monotonic stack to find:
• Previous Greater or Equal: the nearest index to the left where nums[j] >= nums[i], or -1 if none exists.
• Next Greater: the nearest index to the right where nums[j] > nums[i], or n if none exists.
• The number of subarrays where nums[i] is the max is leftCount * rightCount, where leftCount = i - prevGreaterOrEqual[i] and rightCount = nextGreater[i] - i.
• Accumulate nums[i] * leftCount * rightCount into sumMax.

3. Compute Sum of Subarray Minimums

• Similarly, for each element find how many subarrays have nums[i] as their minimum.
• Use a monotonic stack to find:
• Previous Less or Equal: the nearest index to the left where nums[j] <= nums[i], or -1.
• Next Less: the nearest index to the right where nums[j] < nums[i], or n.
• Accumulate nums[i] * leftCount * rightCount into sumMin.

4. Combine the Results

• Return sumMax - sumMin, which equals the sum of all subarray ranges.

Key Insight

By decomposing the range into max and min contributions, each element's contribution to all subarrays can be computed in O(1) using boundary indices from a monotonic stack. The strict vs. non-strict inequality on each side prevents double-counting duplicates. Overall time complexity: O(n), space complexity: O(n).