Sum of Subarray Ranges
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums. The range of a subarray of nums
is the difference between the largest and smallest element in the subarray.
Return _thesum of all subarray ranges of _nums .
A subarray is a contiguous non-empty sequence of elements within an array.
Examples
Example 1
Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.
Example 2
Input: nums = [1,3,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[3], range = 3 - 3 = 0
[3], range = 3 - 3 = 0
[1,3], range = 3 - 1 = 2
[3,3], range = 3 - 3 = 0
[1,3,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.
Example 3
Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.
Constraints
1 <= nums.length <= 1000-10^9 <= nums[i] <= 10^9
Follow-up: Could you find a solution with O(n) time complexity?
Solution
Approach
For each subarray, the range is the difference between the maximum and minimum. Instead of brute force, we can count for each element how many subarrays it is the maximum and how many it is the minimum, and sum up their contributions. This can be done efficiently using monotonic stacks.
For each index, find the previous and next less/greater elements. The number of subarrays where nums[i] is the minimum is (i - prev_less) * (next_less - i), and similarly for maximum. The answer is the sum of all contributions as maximum minus the sum as minimum.
Code
C++
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long res = 0;
// Max contribution
stack<int> st;
for (int i = 0; i <= n; ++i) {
while (!st.empty() && (i == n || nums[st.top()] < (i < n ? nums[i] : INT_MAX))) {
int j = st.top(); st.pop();
int k = st.empty() ? -1 : st.top();
res += (long long)nums[j] * (j - k) * (i - j);
}
st.push(i);
}
// Min contribution
st = stack<int>();
for (int i = 0; i <= n; ++i) {
while (!st.empty() && (i == n || nums[st.top()] > (i < n ? nums[i] : INT_MIN))) {
int j = st.top(); st.pop();
int k = st.empty() ? -1 : st.top();
res -= (long long)nums[j] * (j - k) * (i - j);
}
st.push(i);
}
return res;
}
};
Java
import java.util.*;
class Solution {
public long subArrayRanges(int[] nums) {
int n = nums.length;
long res = 0;
Deque<Integer> st = new ArrayDeque<>();
// Max contribution
for (int i = 0; i <= n; ++i) {
while (!st.isEmpty() && (i == n || nums[st.peek()] < (i < n ? nums[i] : Integer.MAX_VALUE))) {
int j = st.pop();
int k = st.isEmpty() ? -1 : st.peek();
res += (long)nums[j] * (j - k) * (i - j);
}
st.push(i);
}
st.clear();
// Min contribution
for (int i = 0; i <= n; ++i) {
while (!st.isEmpty() && (i == n || nums[st.peek()] > (i < n ? nums[i] : Integer.MIN_VALUE))) {
int j = st.pop();
int k = st.isEmpty() ? -1 : st.peek();
res -= (long)nums[j] * (j - k) * (i - j);
}
st.push(i);
}
return res;
}
}
Kotlin
class Solution {
fun subArrayRanges(nums: IntArray): Long {
val n = nums.size
var res = 0L
val st = ArrayDeque<Int>()
// Max contribution
for (i in 0..n) {
while (st.isNotEmpty() && (i == n || nums[st.last()] < if (i < n) nums[i] else Int.MAX_VALUE)) {
val j = st.removeLast()
val k = if (st.isEmpty()) -1 else st.last()
res += nums[j].toLong() * (j - k) * (i - j)
}
st.addLast(i)
}
st.clear()
// Min contribution
for (i in 0..n) {
while (st.isNotEmpty() && (i == n || nums[st.last()] > if (i < n) nums[i] else Int.MIN_VALUE)) {
val j = st.removeLast()
val k = if (st.isEmpty()) -1 else st.last()
res -= nums[j].toLong() * (j - k) * (i - j)
}
st.addLast(i)
}
return res
}
}
Python
class Solution:
def subArrayRanges(self, nums: list[int]) -> int:
n = len(nums)
res = 0
st = []
# Max contribution
for i in range(n+1):
while st and (i == n or nums[st[-1]] < (nums[i] if i < n else float('inf'))):
j = st.pop()
k = st[-1] if st else -1
res += nums[j] * (j - k) * (i - j)
st.append(i)
st.clear()
# Min contribution
for i in range(n+1):
while st and (i == n or nums[st[-1]] > (nums[i] if i < n else float('-inf'))):
j = st.pop()
k = st[-1] if st else -1
res -= nums[j] * (j - k) * (i - j)
st.append(i)
return res
Rust
impl Solution {
pub fn sub_array_ranges(nums: Vec<i32>) -> i64 {
let n = nums.len();
let mut res = 0i64;
let mut st = Vec::new();
// Max contribution
for i in 0..=n {
while let Some(&j) = st.last() {
if i == n || nums[j] < if i < n { nums[i] } else { i32::MAX } {
st.pop();
let k = *st.last().unwrap_or(&-1);
res += nums[j] as i64 * (j as i64 - k as i64) * (i as i64 - j as i64);
} else { break; }
}
st.push(i as i32);
}
st.clear();
// Min contribution
for i in 0..=n {
while let Some(&j) = st.last() {
if i == n || nums[j] > if i < n { nums[i] } else { i32::MIN } {
st.pop();
let k = *st.last().unwrap_or(&-1);
res -= nums[j] as i64 * (j as i64 - k as i64) * (i as i64 - j as i64);
} else { break; }
}
st.push(i as i32);
}
res
}
}
TypeScript
function subArrayRanges(nums: number[]): number {
const n = nums.length;
let res = 0;
const st: number[] = [];
// Max contribution
for (let i = 0; i <= n; ++i) {
while (st.length && (i === n || nums[st[st.length-1]] < (i < n ? nums[i] : Infinity))) {
const j = st.pop()!;
const k = st.length ? st[st.length-1] : -1;
res += nums[j] * (j - k) * (i - j);
}
st.push(i);
}
st.length = 0;
// Min contribution
for (let i = 0; i <= n; ++i) {
while (st.length && (i === n || nums[st[st.length-1]] > (i < n ? nums[i] : -Infinity))) {
const j = st.pop()!;
const k = st.length ? st[st.length-1] : -1;
res -= nums[j] * (j - k) * (i - j);
}
st.push(i);
}
return res;
}
Complexity
- ⏰ Time complexity:
O(n) - 🧺 Space complexity:
O(n)