Watch 10 video solutions for Sum of Subarray Ranges, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by take U forward has 141,575 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: You are given an integer array and must compute the sum of ranges for all subarrays. The range of a subarray equals max(subarray) - min(subarray). The task is to efficiently aggregate this value across every possible subarray.
Approach 1: Brute Force Expansion (O(n²) time, O(1) space)
Start a subarray at each index and expand it to the right. While expanding, maintain the current minimum and maximum values. Each time the window grows, update min and max, then add max - min to the result. This avoids recomputing min and max from scratch but still requires checking every subarray pair (i, j). The algorithm runs in O(n²) time with constant extra space. This approach is straightforward and useful for validating logic, but it becomes slow for large arrays because the number of subarrays grows quadratically.
Approach 2: Monotonic Stack Contribution Method (O(n) time, O(n) space)
The key observation is that each element contributes to multiple subarrays as both a maximum and a minimum. Instead of enumerating subarrays, count how many subarrays treat a value as their maximum and how many treat it as their minimum. The difference between these contributions determines its impact on the final sum.
Use monotonic stacks to find the previous and next greater elements for maximum contribution and the previous and next smaller elements for minimum contribution. For an index i, the number of subarrays where nums[i] is the maximum equals (i - prevGreater) * (nextGreater - i). Apply a similar calculation using smaller elements to count when it acts as the minimum. Multiply each count by the element value and accumulate the difference.
This transforms the problem into two linear scans using stack operations such as push, pop, and index tracking. Each element enters and leaves the stack once, producing O(n) time complexity and O(n) auxiliary space. The technique is widely used in problems involving subarray contributions and boundary discovery in stack-based algorithms on an array.
Recommended for interviews: Interviewers expect the monotonic stack solution because it demonstrates understanding of contribution counting and boundary discovery. Implementing the brute force approach first shows problem comprehension, but the O(n) stack solution shows strong algorithmic intuition and familiarity with advanced array techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(n²) | O(1) | Useful for understanding the problem or verifying correctness on small arrays |
| Monotonic Stack Contribution | O(n) | O(n) | Best choice for large inputs and expected solution in coding interviews |