Sum of Subarray Ranges
Medium · Stack & Strings · Array · Stack · Monotonic Stack
Problem
You are given an integer array nums. The range of a subarray is its largest element minus its smallest element.
Return the sum of the ranges of all non-empty contiguous subarrays of nums.
The answer can exceed 32 bits, so use a 64-bit integer where your language needs one.
Examples
Input: nums = [2,4,1] Output: 8
Single elements have range 0, while [2,4], [4,1] and [2,4,1] have ranges 2, 3 and 3.
Input: nums = [1,-2,5] Output: 17
The ranges of [1,-2], [-2,5] and [1,-2,5] are 3, 7 and 7.
Input: nums = [3,3,3] Output: 0
Every subarray has equal elements, so every range is 0.
Constraints
- 1 <= len(nums) <= 1000
- -10^9 <= nums[i] <= 10^9
Approaches
- Baseline: extend each start, tracking max and min — time O(n²), space O(1)
Follow-up
What about subsequences instead of subarrays? Then order stops mattering: sort, and each element is the maximum of 2^i subsequences and the minimum of 2^(n-1-i) (see the use case “Sum of ranges over every subsequence”).
Related problems
Start free on Cariara · Coding problems · System design studio
