Sum of Subarray Ranges
Sum of Subarray Ranges is a medium monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (contribution with monotonic stacks), runs in O(n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (every subarray, scan it) up.
Problem
You are given an integer array nums. The range of a subarray is the difference between its largest and its smallest element.
Return the sum of the ranges of all non-empty contiguous subarrays of nums.
Examples
Example 1
- Input
nums = [2, 5, 1]- Output
11- Why
- The ranges are 0, 0, 0 for the single elements, 3 for [2,5], 4 for [5,1] and 4 for [2,5,1]; 3 + 4 + 4 = 11.
Example 2
- Input
nums = [3, 3, 3]- Output
0- Why
- Every subarray has equal largest and smallest values.
Example 3
- Input
nums = [-2, 4]- Output
6- Why
- Only [-2, 4] has a non-zero range: 4 - (-2) = 6.
Constraints
1 <= nums.length <= 1000-10^9 <= nums[i] <= 10^9- The answer fits in a 64-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every subarray, scan it) | O(n³) | O(1) |
| Better (extend each start with running max and min) | O(n²) | O(1) |
| Optimal (contribution with monotonic stacks) | O(n) | O(n) |
1Brute force (every subarray, scan it)
O(n³)O(n²) subarrays, each scanned in O(n).O(1)Only a few counters.Enumerate every pair of ends (i, j) and scan the subarray between them to find its largest and smallest value. Add their difference to the total.
- For each i, for each j >= i: scan nums[i..j] for max and min.
- Add max - min to the total.
class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
long total = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int max = nums[i], min = nums[i];
for (int k = i; k <= j; k++) {
max = Math.max(max, nums[k]);
min = Math.min(min, nums[k]);
}
total += (long) max - min;
}
}
return total;
}
}class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
n = len(nums)
total = 0
for i in range(n):
for j in range(i, n):
hi = lo = nums[i]
for k in range(i, j + 1):
hi = max(hi, nums[k])
lo = min(lo, nums[k])
total += hi - lo
return totalclass Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long total = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int mx = nums[i], mn = nums[i];
for (int k = i; k <= j; k++) {
mx = max(mx, nums[k]);
mn = min(mn, nums[k]);
}
total += (long long) mx - mn;
}
}
return total;
}
};function subArrayRanges(nums) {
const n = nums.length;
let total = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let max = nums[i], min = nums[i];
for (let k = i; k <= j; k++) {
max = Math.max(max, nums[k]);
min = Math.min(min, nums[k]);
}
total += max - min;
}
}
return total;
}2Better (extend each start with running max and min)
O(n²)Each of the O(n²) subarrays is handled in O(1).O(1)Only the running values.Fix the left end i and move the right end j forward. The maximum and minimum of nums[i..j] follow from those of nums[i..j-1] with one comparison each, so no inner scan is needed.
- For each i: max = min = nums[i].
- For each j from i to n - 1: update max and min with nums[j], add max - min.
class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
long total = 0;
for (int i = 0; i < n; i++) {
int max = nums[i], min = nums[i];
for (int j = i; j < n; j++) {
max = Math.max(max, nums[j]);
min = Math.min(min, nums[j]);
total += (long) max - min;
}
}
return total;
}
}class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
n = len(nums)
total = 0
for i in range(n):
hi = lo = nums[i]
for j in range(i, n):
hi = max(hi, nums[j])
lo = min(lo, nums[j])
total += hi - lo
return totalclass Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long total = 0;
for (int i = 0; i < n; i++) {
int mx = nums[i], mn = nums[i];
for (int j = i; j < n; j++) {
mx = max(mx, nums[j]);
mn = min(mn, nums[j]);
total += (long long) mx - mn;
}
}
return total;
}
};function subArrayRanges(nums) {
const n = nums.length;
let total = 0;
for (let i = 0; i < n; i++) {
let max = nums[i], min = nums[i];
for (let j = i; j < n; j++) {
max = Math.max(max, nums[j]);
min = Math.min(min, nums[j]);
total += max - min;
}
}
return total;
}3Optimal (contribution with monotonic stacks)
O(n)Each index is pushed and popped once per scan, and there are two scans.O(n)The stack can hold all n indices.Split the answer into the sum of subarray maximums minus the sum of subarray minimums. nums[i] is the maximum of exactly (i - left) · (right - i) subarrays, where left is the previous index with a value >= nums[i] and right the next index with a value > nums[i] (the asymmetric tie rule counts each subarray once). A decreasing stack finds both neighbours: when an index is popped, the index that pops it is right and the index below it is left. The minimum side is the same with the comparison flipped.
- sumMax: scan i from 0 to n (i == n acts as +infinity). While the stack is not empty and (i == n or nums[top] < nums[i]): pop mid, left = new top or -1, add nums[mid] · (mid - left) · (i - mid). Push i.
- sumMin: same scan with (i == n or nums[top] > nums[i]).
- Return sumMax - sumMin.
class Solution {
public long subArrayRanges(int[] nums) {
return sumOf(nums, true) - sumOf(nums, false);
}
private long sumOf(int[] nums, boolean wantMax) {
int n = nums.length;
long sum = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
while (!stack.isEmpty() && (i == n || (wantMax ? nums[stack.peek()] < nums[i] : nums[stack.peek()] > nums[i]))) {
int mid = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
sum += (long) nums[mid] * (mid - left) * (i - mid);
}
stack.push(i);
}
return sum;
}
}class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
return self.sum_of(nums, True) - self.sum_of(nums, False)
def sum_of(self, nums: List[int], want_max: bool) -> int:
n = len(nums)
total = 0
stack = []
for i in range(n + 1):
while stack and (i == n or (nums[stack[-1]] < nums[i] if want_max else nums[stack[-1]] > nums[i])):
mid = stack.pop()
left = stack[-1] if stack else -1
total += nums[mid] * (mid - left) * (i - mid)
stack.append(i)
return totalclass Solution {
long long sumOf(vector<int>& nums, bool wantMax) {
int n = nums.size();
long long sum = 0;
vector<int> stack;
for (int i = 0; i <= n; i++) {
while (!stack.empty() && (i == n || (wantMax ? nums[stack.back()] < nums[i] : nums[stack.back()] > nums[i]))) {
int mid = stack.back();
stack.pop_back();
int left = stack.empty() ? -1 : stack.back();
sum += (long long) nums[mid] * (mid - left) * (i - mid);
}
stack.push_back(i);
}
return sum;
}
public:
long long subArrayRanges(vector<int>& nums) {
return sumOf(nums, true) - sumOf(nums, false);
}
};function subArrayRanges(nums) {
const sumOf = (wantMax) => {
const n = nums.length;
let sum = 0;
const stack = [];
for (let i = 0; i <= n; i++) {
while (stack.length > 0 && (i === n || (wantMax ? nums[stack[stack.length - 1]] < nums[i] : nums[stack[stack.length - 1]] > nums[i]))) {
const mid = stack.pop();
const left = stack.length > 0 ? stack[stack.length - 1] : -1;
sum += nums[mid] * (mid - left) * (i - mid);
}
stack.push(i);
}
return sum;
};
return sumOf(true) - sumOf(false);
}Edge cases to test
- A single element: the answer is 0
- Equal values next to each other (ties must not be counted twice in the stack method)
- Strictly increasing or strictly decreasing arrays
- Values near ±10^9: the sum needs 64-bit integers
Hints
Hint 1
The range of one subarray is its maximum minus its minimum, so the total is (sum of all subarray maximums) - (sum of all subarray minimums).
Hint 2
If you fix the left end and extend to the right, the running max and min update in O(1) per step.
Hint 3
For the O(n) solution, count for each nums[i] in how many subarrays it is the maximum: that is (distance to the previous larger element) × (distance to the next larger element). Monotonic stacks find those neighbours.
FAQ
What is the best time complexity for Sum of Subarray Ranges?
Optimal (contribution with monotonic stacks) runs in O(n) time and O(n) extra space. Each index is pushed and popped once per scan, and there are two scans.
Which pattern does Sum of Subarray Ranges use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Sum of Subarray Ranges?
Yes. Brute force (every subarray, scan it) takes O(n³) time and O(1) space. Enumerate every pair of ends (i, j) and scan the subarray between them to find its largest and smallest value.
Which edge cases should I test for Sum of Subarray Ranges?
A single element: the answer is 0; Equal values next to each other (ties must not be counted twice in the stack method); Strictly increasing or strictly decreasing arrays; Values near ±10^9: the sum needs 64-bit integers.