AlgoInsight

DSA problem

Sum of Subarray Ranges

MediumMonotonic StackPattern: Monotonic Stacktop600AmazonGoogleMicrosoftBloomberg

Given an integer array nums, the range of a subarray is the difference between its largest and smallest element. Return the sum of the ranges of every contiguous subarray of nums.

The brute force enumerates all O(n²) subarrays and computes max and min on the fly while extending the right endpoint, giving O(n²) time and O(1) extra space. That is acceptable for the given constraint n <= 1000 and is sometimes the expected solution.

The follow-up asks for an O(n) solution, and the elegant approach uses the same contribution technique as "Sum of Subarray Minimums" applied twice. The sum of ranges equals the sum of subarray maxes minus the sum of subarray mins. For each index i, count the subarrays where it is the maximum (using "previous greater" and "next greater-or-equal") and the subarrays where it is the minimum (using "previous less" and "next less-or-equal"). Multiply by nums[i] and add or subtract appropriately.

Both subproblems use a monotonic stack and run in O(n). Because values can be negative, no modulus is required — just use 64-bit arithmetic to be safe.

Examples

Example 1
Input: nums = [1,2,3]
Output: 4
Explanation: Subarrays: [1]→0, [2]→0, [3]→0, [1,2]→1, [2,3]→1, [1,2,3]→2. Sum = 4.
Example 2
Input: nums = [1,3,3]
Output: 4
Explanation: Subarrays: [1]→0, [3]→0, [3]→0, [1,3]→2, [3,3]→0, [1,3,3]→2. Sum = 4.
Example 3
Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: Compute (max - min) for all 15 subarrays; the total is 59.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

monotonic-stackstackarraycontribution-technique

Browse all DSA problems