Sum of Subarray Ranges
Understanding the Problem
We need to look at every contiguous subarray of the input, compute the difference between its maximum and minimum element, and sum all those differences together.
For a single-element subarray, the range is 0 since the max and min are the same element. For longer subarrays, the range grows as the spread between the largest and smallest elements increases.
One reframing leads directly to the optimal solution. The sum of all ranges can be split into two separate sums:
Sum of (max - min) over all subarrays = Sum of all subarray maximums - Sum of all subarray minimums
This decomposition turns one problem into two independent ones: how many times does each element act as a subarray maximum, and how many times does it act as a subarray minimum? Answering both efficiently avoids enumerating subarrays at all.
Key Constraints:
1 <= nums.length <= 1000-- With n up to 1000, an O(n^2) brute force does about 5 * 10^5 operations and passes well within time limits. The monotonic stack approach runs in O(n) and scales to much larger inputs.-10^9 <= nums[i] <= 10^9-- A single range can be as large as 2 10^9, and there are up to n(n+1)/2 ≈ 5 10^5 subarrays. The total can reach roughly 10^15, which overflows a 32-bit integer, so the sum must accumulate in a 64-bit type (long).
Approach 1: Brute Force (Enumerate All Subarrays)
Intuition
Enumerate every subarray using two nested loops. For each subarray defined by indices i (start) and j (end), track the running minimum and maximum as j extends to the right. The range is max - min, which gets added to the running total.
Updating min and max incrementally as j moves, rather than rescanning the whole subarray each time, avoids a third nested loop and keeps the work at O(n^2).
Algorithm
- Initialize
totalSum = 0. - For each starting index
ifrom 0 to n-1: - Set
currentMin = nums[i]andcurrentMax = nums[i]. - For each ending index
jfromito n-1: - Update
currentMin = min(currentMin, nums[j]). - Update
currentMax = max(currentMax, nums[j]). - Add
currentMax - currentMintototalSum. - Return
totalSum.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Two nested loops, each running up to n iterations. For each pair (i, j) we do O(1) work to update min, max, and the sum.
- Space Complexity: O(1). Only a few tracking variables regardless of input size.
This approach passes within the given constraints, but it repeats work. Many subarrays share the same minimum or maximum element, and the nested loops rediscover that for each subarray separately. The next approach computes each element's total contribution as a minimum and as a maximum directly, which brings the time down to O(n).
Approach 2: Monotonic Stack (Optimal)
Intuition
Instead of computing max - min for each subarray, split the sum: Sum of all ranges = (sum of subarray maximums) - (sum of subarray minimums). The question becomes: for each element nums[i], how many subarrays have nums[i] as their maximum, and how many have it as their minimum?
For nums[i] to be the minimum of a subarray, every other element in that subarray must be greater than or equal to nums[i]. That means finding the boundaries: how far left and right can the subarray extend from index i before hitting an element smaller than nums[i]? A monotonic stack finds those boundaries in linear time.
Let prevSmaller be the index of the nearest element to the left that is strictly smaller than nums[i], and nextSmaller the nearest element to the right that is smaller than or equal to nums[i]. Then nums[i] is the minimum of exactly (i - prevSmaller) * (nextSmaller - i) subarrays: any start in [prevSmaller+1, i] paired with any end in [i, nextSmaller-1]. A decreasing stack applies the same counting for maximums. The asymmetry in the comparisons (strict on one side, non-strict on the other) is what handles duplicates without double-counting, explained below.
When nums[i] is popped from the minimums stack, the element left on top is its nearest strictly smaller element on the left, and the index i that triggered the pop is its nearest smaller-or-equal element on the right. This follows from the pop condition nums[stack[top]] >= currentVal: an equal value arriving on the right does trigger a pop, so the right boundary stops at an equal element, while the element that remains below on the stack is strictly smaller.
With several equal values, this split assigns each subarray's minimum to exactly one of them. Take [1, 3, 3]: the subarray [3, 3] (indices 1 and 2) has minimum 3. The left 3 at index 1 has its right boundary at index 2, because the equal value there triggers its pop, so its end positions are limited to index 1 only. The right 3 at index 2 extends its start back to index 1, so [3, 3] is counted once, under index 2. Without the strict/non-strict split, both copies would claim that subarray and the sum would be too high.
Algorithm
- Compute the sum of subarray minimums: For each index
i, use a monotonic increasing stack to find the distance to the previous strictly smaller element (leftCount) and the next smaller-or-equal element (rightCount). Eachnums[i]contributesnums[i] * leftCount * rightCount. - Compute the sum of subarray maximums: For each index
i, use a monotonic decreasing stack to find the distance to the previous strictly greater element (leftCount) and the next greater-or-equal element (rightCount). Eachnums[i]contributesnums[i] * leftCount * rightCount. - Return
sumOfMaximums - sumOfMinimums.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each element is pushed onto and popped from each stack exactly once. The total work across all iterations is O(n) for the minimums stack and O(n) for the maximums stack.
- Space Complexity: O(n). Each stack can hold at most n elements at any point.