Sum of Subarray Ranges
MedPrompt
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 the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
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-109 <= nums[i] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible subarrays using nested loops. For each subarray, it keeps track of the minimum and maximum elements found so far and calculates the range. The sum of these ranges gives the final answer.
Algorithm
- Initialize a variable
totalRangeSumto 0. - Iterate through the array with an index
ifrom 0 ton-1. This indexiwill be the starting point of our subarrays. - Inside this loop, initialize
minVal = nums[i]andmaxVal = nums[i]. - Start a nested loop with an index
jfromiton-1. This indexjwill be the ending point of our subarrays. - In the inner loop, for each subarray
nums[i...j], update theminValandmaxValby comparing with the current elementnums[j].minVal = Math.min(minVal, nums[j])maxVal = Math.max(maxVal, nums[j])
- Calculate the range for the current subarray
nums[i...j]asmaxVal - minVal. - Add this range to the
totalRangeSum. - After the loops complete,
totalRangeSumwill hold the sum of all subarray ranges. Return this value.
Walkthrough
The most straightforward way to solve this problem is to generate every possible contiguous subarray, find the minimum and maximum value within each, calculate the range, and sum up all the ranges.
We can use two nested loops to define the start and end of each subarray. The outer loop with index i iterates from 0 to n-1, fixing the starting point of the subarrays. The inner loop with index j iterates from i to n-1, extending the subarray to the right. For each subarray starting at i, we maintain two variables, currentMin and currentMax. As the inner loop progresses from j = i to n-1, we consider the subarray nums[i...j]. We update currentMin and currentMax with nums[j]. The range for the subarray nums[i...j] is currentMax - currentMin, which we add to a running total. After both loops complete, this total sum is our answer.
class Solution { public long subarrayRanges(int[] nums) { long totalRangeSum = 0; int n = nums.length; for (int i = 0; i < n; i++) { int minVal = nums[i]; int maxVal = nums[i]; for (int j = i; j < n; j++) { minVal = Math.min(minVal, nums[j]); maxVal = Math.max(maxVal, nums[j]); totalRangeSum += (long) maxVal - minVal; } } return totalRangeSum; }}Complexity
Time
O(n^2) where `n` is the number of elements in `nums`. The two nested loops result in a quadratic time complexity. The outer loop runs `n` times, and the inner loop runs on average `n/2` times.
Space
O(1) because we only use a constant amount of extra space for variables like `totalRangeSum`, `minVal`, and `maxVal`.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space apart from a few variables.
Cons
Less efficient than the optimal solution.
For larger constraints on
n, this approach would be too slow and result in a Time Limit Exceeded error.
This optimal approach solves the problem in linear time by reformulating it. The sum of all subarray ranges, Sum(max - min), is equivalent to Sum(max) - Sum(min). We can calculate the sum of maximums and the sum of minimums for all subarrays separately. A monotonic stack is a key data structure used to efficiently determine, for each element nums[i], the number of subarrays where it serves as the maximum or minimum.
Algorithm
- The core idea is that
Sum(max(subarray) - min(subarray))equalsSum(max(subarray)) - Sum(min(subarray)). - We calculate
sumOfMaxs(sum of maximums of all subarrays) andsumOfMins(sum of minimums of all subarrays) separately. - To calculate
sumOfMaxs: a. Initialize an empty stack andsumOfMaxs = 0. b. Iterate with an indexifrom0ton(inclusive, to handle elements remaining in the stack). c. While the stack is not empty and the element at the top of the stack is less than or equal to the current element (i == nornums[stack.peek()] <= nums[i]): i. Pop an indexmidfrom the stack. Thisnums[mid]is a local maximum. ii. The left boundary for its subarrays is the index at the new top of the stack (or -1 if empty). iii. The right boundary is the current indexi. iv. The number of subarrays wherenums[mid]is the maximum is(mid - left) * (i - mid). v. Add(long)nums[mid] * (mid - left) * (i - mid)tosumOfMaxs. d. Ifi < n, pushionto the stack. - To calculate
sumOfMins, repeat step 3 but with the comparison reversed: while the stack is not empty andnums[stack.peek()] >= nums[i]. - The final result is
sumOfMaxs - sumOfMins.
Walkthrough
This approach is based on a clever observation: the sum of ranges of all subarrays can be split into two independent problems: (sum of all subarray maximums) - (sum of all subarray minimums).
We can calculate these two sums separately. For each element nums[i], we find its total contribution to sumOfMaxs and sumOfMins. The contribution is nums[i] multiplied by the number of subarrays where it is the maximum (or minimum).
To count these subarrays accurately, especially when duplicate values exist, we must establish a consistent rule to avoid overcounting. For instance, we can decide that nums[i] is the designated maximum of a subarray only if it's the last occurrence of that value within that subarray. This means we need to find the boundaries (left, right) for nums[i] such that all elements between left and i are less than or equal to nums[i], and all elements between i and right are strictly less than nums[i].
A monotonic stack is the perfect tool for finding these boundaries for every element in O(n) time. We use one pass with a monotonic stack to calculate sumOfMaxs and another pass to calculate sumOfMins.
For sumOfMaxs, we maintain a stack of indices in decreasing order of their values in nums. When we encounter an element nums[i] that is greater than the element at the top of the stack, we know nums[i] is the 'next greater element' for the popped element. This allows us to determine the boundaries and calculate the contribution on the fly.
import java.util.Stack; class Solution { public long subarrayRanges(int[] nums) { int n = nums.length; long sumOfMaxs = 0; long sumOfMins = 0; Stack<Integer> stack = new Stack<>(); // Calculate sum of maximums of all subarrays for (int i = 0; i <= n; i++) { while (!stack.isEmpty() && (i == n || nums[stack.peek()] <= nums[i])) { int mid = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int right = i; sumOfMaxs += (long) nums[mid] * (mid - left) * (right - mid); } if (i < n) { stack.push(i); } } stack.clear(); // Calculate sum of minimums of all subarrays for (int i = 0; i <= n; i++) { while (!stack.isEmpty() && (i == n || nums[stack.peek()] >= nums[i])) { int mid = stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); int right = i; sumOfMins += (long) nums[mid] * (mid - left) * (right - mid); } if (i < n) { stack.push(i); } } return sumOfMaxs - sumOfMins; }}Complexity
Time
O(n). Each index is pushed onto and popped from the stack at most once for each of the two main loops (one for sum of maxes, one for sum of mins). Thus, the total time complexity is linear with respect to the input size.
Space
O(n) in the worst case. The stack can store up to `n` indices if the input array is, for example, strictly increasing (for sum of mins) or strictly decreasing (for sum of maxs).
Trade-offs
Pros
Highly efficient with linear time complexity, making it the optimal solution.
Satisfies the follow-up question for an O(n) solution.
Cons
More complex to understand and implement correctly compared to the O(n^2) approach.
The logic for handling boundaries and duplicates with the monotonic stack can be subtle and error-prone.
Solutions
Solution
class Solution {public long subArrayRanges(int[] nums) { long ans = 0; int n = nums.length; for (int i = 0; i < n - 1; ++i) { int mi = nums[i], mx = nums[i]; for (int j = i + 1; j < n; ++j) { mi = Math.min(mi, nums[j]); mx = Math.max(mx, nums[j]); ans += (mx - mi); } } return ans; }}class Solution {public: long long subArrayRanges(vector<int> &nums) { long long ans = 0; int n = nums.size(); for (int i = 0; i < n - 1; ++i) { int mi = nums[i], mx = nums[i]; for (int j = i + 1; j < n; ++j) { mi = min(mi, nums[j]); mx = max(mx, nums[j]); ans += (mx - mi); } } return ans; }};class Solution: def subArrayRanges(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(n - 1): mi = mx = nums[i] for j in range(i + 1, n): mi = min(mi, nums[j]) mx = max(mx, nums[j]) ans += mx - mi return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.