The range of a subarray is its maximum minus its minimum. Given an array nums, return the sum of the ranges over all contiguous subarrays.
Hints
· Stuck? Reveal one nudge at a time.
A subarray's range is max - min, so the total splits into sum of maxes minus sum of mins.
Each sum is the contribution trick from Sum of Subarray Minimums, mirrored for maximums.
Two monotonic-stack passes per sum; subtract the two totals.
Common doubts
Summation is linear: the sum of (max - min) over subarrays equals the sum of maxes minus the sum of mins, and each can be counted separately.
Just flip the comparisons: previous strictly-greater and next greater-or-equal for max, versus previous strictly-smaller and next smaller-or-equal for min.
No, but the total exceeds 32 bits, so accumulate in a 64-bit integer.
Interview follow-ups
· What an interviewer asks next.
Yes — the exact answer fits in signed 64-bit; just ensure every intermediate product uses 64-bit arithmetic.
Add the two contribution sums instead of subtracting them.
Fun facts
Decomposing an aggregate into independent per-element contributions is one of the most reusable competitive-programming moves.
This problem is literally 'Sum of Subarray Minimums' run twice with the comparisons flipped.
Asked at
AmazonGoogle
Frequently Sometimes Occasionally
Example 1
Input: nums = [1,2,3]
Output: 4
Subarray ranges are 0,1,2,0,1,0; their sum is 4.
A subarray's range is max - min, so the total is (sum of all subarray maximums) - (sum of all subarray minimums). Each of those two sums is the same contribution-via-monotonic-stack trick from Sum of Subarray Minimums — just mirrored for maximums. Compute both in O(n) and subtract.
Prerequisites
Before you start
· Concepts used directly in the solution.
Sum of subarray minimums. Counting how many subarrays each element is the minimum of, via previous/next smaller boundaries.
Linearity. Sum of (max - min) = sum of max - sum of min, computed independently.
Clarifying questions
Questions to ask first
· Signals seniority before you write a line of code.
The value
“Can the total exceed 32 bits?”
Yes — accumulate in a 64-bit integer.
“Do single-element subarrays contribute?”
Their range is 0 (max == min), so they add nothing.
The ideal opening — say it like this
1
Range is max minus min, so the answer is the sum of subarray maxes minus the sum of subarray mins.
2
Each sum is the contribution trick: every element times how many subarrays it's the max (or min) of.
3
Two monotonic-stack passes each, and I subtract — all O(n).
Understand the problem
Worked example — nums = [1, 2, 3]
sum of maxes: subarray maxes 1,2,3, 2,3, 3 -> 1+2+3+2+3+3 = 14
sum of mins: subarray mins 1,2,3, 1,2, 1 -> 1+2+3+1+2+1 = 10
answer = 14 - 10 = 4
Key observations
1Aha
Range sum splits into max sum minus min sum
Because range is a difference, the total decomposes into two independent contribution sums.
2Aha
Max mirrors min
The maximum contribution uses previous strictly-greater and next greater-or-equal boundaries — the same code as minimums with the comparisons flipped.
3Aha
No modulo, but use 64-bit
The answer fits in a signed 64-bit integer, but not 32-bit — accumulate carefully.
Brute force vs optimal
Every subarray
Two contribution sums
Idea
Track running max and min, add their difference
sum of maxes - sum of mins via monotonic stacks
Time
O(n^2)
O(n)
Space
O(1)
O(n)
Full code is in the Approaches selector below.
Summary
Key takeaway
Sum of ranges = sum of subarray maxes - sum of subarray mins. Each is the contribution trick (element x left-span x right-span) via two monotonic-stack passes, mirrored for max vs min. O(n), 64-bit accumulation.
answer = contributionSum(max) - contributionSum(min)
where contributionSum uses previous/next {strictly-greater,>=} for max
and previous/next {strictly-smaller,<=} for min
Ready to try it? Write and run your solution in the browser.Solve this problem →
