Sum of Subarray Ranges
Problem
Return the sum of (max − min) over every contiguous subarray of nums. Use two monotonic-stack passes: each element's contribution to sum-of-maxes minus sum-of-mins, weighted by counts of subarrays where it dominates.
nums = [1, 2, 3]4def sub_array_ranges(nums):
n = len(nums)
total = 0
for i in range(n):
mn = mx = nums[i]
for j in range(i, n):
mn = min(mn, nums[j])
mx = max(mx, nums[j])
total += mx - mn
return totalfunction subArrayRanges(nums) {
const n = nums.length;
let total = 0;
for (let i = 0; i < n; i++) {
let mn = nums[i], mx = nums[i];
for (let j = i; j < n; j++) {
mn = Math.min(mn, nums[j]);
mx = Math.max(mx, nums[j]);
total += mx - mn;
}
}
return total;
}class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
long total = 0;
for (int i = 0; i < n; i++) {
int mn = nums[i], mx = nums[i];
for (int j = i; j < n; j++) {
mn = Math.min(mn, nums[j]);
mx = Math.max(mx, nums[j]);
total += mx - mn;
}
}
return total;
}
}long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long total = 0;
for (int i = 0; i < n; i++) {
int mn = nums[i], mx = nums[i];
for (int j = i; j < n; j++) {
mn = min(mn, nums[j]);
mx = max(mx, nums[j]);
total += mx - mn;
}
}
return total;
}Explanation
The range of a subarray is its max minus its min, and we want to add this up over every contiguous subarray. The shown solution takes the clear, direct route: try every subarray and track its min and max as it grows.
The outer loop picks a start index i. The inner loop extends the end index j one step at a time. As we add each new element, we update mn = min(mn, nums[j]) and mx = max(mx, nums[j]), then add mx - mn to the running total.
This works because every subarray starting at i is built by extending the previous one by one element, so the running min and max stay correct without rescanning. We simply accumulate each subarray's range as we go.
Example: nums = [1, 2, 3]. Single elements add 0 each. [1,2] adds 1, [2,3] adds 1, and [1,2,3] adds 3 - 1 = 2. Total is 0+0+0+1+1+2 = 4.
There are about n²/2 subarrays and each takes constant work, so this is an O(n²) approach (a monotonic-stack version can reach O(n)).