Sum of Subarray Ranges — Solution in Python, Java & C++
Sum of Subarray Ranges solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Sum of Subarray Ranges is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The range of a subarray is the difference between its largest and smallest element.
Given an integer array nums, return the sum of the ranges of all its contiguous non-empty subarrays.
Example 1
Input: nums = [1,2,3]
Output: 4
Explanation: The ranges are 0,0,0,1,1,2.
Example 2
Input: nums = [1,3,3]
Output: 4
Example 3
Input: nums = [4,-2,-3,4,1]
Output: 59
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Follow-up: The O(n²) sweep is straightforward. Can you do it in O(n) with two monotonic stacks — sum of maximums minus sum of minimums?
Hints for Sum of Subarray Ranges
Hint 1
Fix the left end and extend right, keeping a running minimum and maximum.
Hint 2
Each extension contributes
max - minin constant time, giving O(n²).Hint 3
For O(n), note the answer is the sum of subarray maximums minus the sum of subarray minimums, each computable with a monotonic stack.
How to solve Sum of Subarray Ranges
Fix the left end and extend right, keeping a running min and max; each extension adds max - min in O(1).
Approach
- For each
i, setlo = hi = nums[i]. - For each
j >= i, updatelo,hiand addhi - lo.
Why it works
Every subarray is visited exactly once, and its range is maintained incrementally as it grows.
Complexity
- Time —
O(n²) - Space —
O(1)
Pitfalls
- For O(n), compute Σ subarray maximums minus Σ subarray minimums with two monotonic-stack passes.
Reference solution
Python
def subArrayRanges(nums) -> int:
total = 0
n = len(nums)
for i in range(n):
lo = hi = nums[i]
for j in range(i, n):
lo = min(lo, nums[j])
hi = max(hi, nums[j])
total += hi - lo
return totalJava
public static int subArrayRanges(int[] nums) {
int total = 0;
for (int i = 0; i < nums.length; i++) {
int lo = nums[i], hi = nums[i];
for (int j = i; j < nums.length; j++) {
lo = Math.min(lo, nums[j]);
hi = Math.max(hi, nums[j]);
total += hi - lo;
}
}
return total;
}C++
int subArrayRanges(vector<int>& nums) {
int total = 0;
int n = (int) nums.size();
for (int i = 0; i < n; i++) {
int lo = nums[i], hi = nums[i];
for (int j = i; j < n; j++) {
lo = min(lo, nums[j]);
hi = max(hi, nums[j]);
total += hi - lo;
}
}
return total;
}JavaScript
var subArrayRanges = function(nums) {
let total = 0;
for (let i = 0; i < nums.length; i++) {
let lo = nums[i], hi = nums[i];
for (let j = i; j < nums.length; j++) {
if (nums[j] < lo) lo = nums[j];
if (nums[j] > hi) hi = nums[j];
total += hi - lo;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure