Total High-Low Spread of Every Subarray
Solve this Problemarr, define a subarray's "spread" as its maximum value minus its minimum value. Find the sum of the spreads of every contiguous subarray.
Since spread = max − min, the total sum splits cleanly in two: (sum of every subarray's maximum) minus (sum of every subarray's minimum). Each of those two sums is exactly the "sum of subarray minimums" problem — once directly, and once with every comparison flipped to find maximums instead. Each is solved by asking, per element, "in how many subarrays is this element the min (or max)?" — answered with a monotonic stack locating the nearest smaller (or greater) neighbor on each side in a single linear pass. Four linear passes total replace the brute force's quadratic enumeration of every subarray.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arr.length ≤ 12 - ◆
1 ≤ arr[i] ≤ 100 - ◆
The answer fits comfortably in a 32-bit signed integer for this input size
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Track the Running Min and Max for Every Start
BruteFor every starting index i, extend the subarray one element at a time toward the end, keeping a running minimum and a running maximum as it grows. Every extension adds exactly one new subarray, and its spread (max−min) can be added to the total as soon as it's computed. This visits every one of the O(n²) subarrays individually, without any shortcut.
O(n²)O(1)1class Solution {
2 public int sumSubarrayRanges(int[] arr) {
3 int n = arr.length;
4 long sum = 0;
5 for (int i = 0; i < n; i++) {
6 int mn = arr[i], mx = arr[i];
7 for (int j = i; j < n; j++) {
8 mn = Math.min(mn, arr[j]);
9 mx = Math.max(mx, arr[j]);
10 sum += (mx - mn);
11 }
12 }
13 return (int) sum;
14 }
15}Optimal — Sum of Subarray Maximums Minus Sum of Subarray Minimums
OptimalSince (max−min) summed over every subarray equals (sum of every subarray's max) minus (sum of every subarray's min), the two totals can be computed completely separately, each with the same "count each element's contribution" trick: for every element, find how many subarrays it is the minimum (or maximum) of, using a monotonic stack to locate the nearest smaller/greater neighbor on each side in a single pass. Four linear passes total (two bounds for the min-sum, two for the max-sum) replace the brute force's quadratic subarray enumeration entirely.
O(n)O(n)1class Solution {
2 public int sumSubarrayRanges(int[] arr) {
3 int n = arr.length;
4 long sum = 0;
5
6 int[] prevSmaller = new int[n];
7 int[] nextSmallerEq = new int[n];
8 Deque<Integer> stack = new ArrayDeque<>();
9 for (int i = 0; i < n; i++) {
10 while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
11 prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
12 stack.push(i);
13 }
14 stack.clear();
15 for (int i = n - 1; i >= 0; i--) {
16 while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
17 nextSmallerEq[i] = stack.isEmpty() ? n : stack.peek();
18 stack.push(i);
19 }
20 for (int i = 0; i < n; i++) {
21 sum -= (long) arr[i] * (i - prevSmaller[i]) * (nextSmallerEq[i] - i);
22 }
23
24 int[] prevGreater = new int[n];
25 int[] nextGreaterEq = new int[n];
26 stack.clear();
27 for (int i = 0; i < n; i++) {
28 while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) stack.pop();
29 prevGreater[i] = stack.isEmpty() ? -1 : stack.peek();
30 stack.push(i);
31 }
32 stack.clear();
33 for (int i = n - 1; i >= 0; i--) {
34 while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) stack.pop();
35 nextGreaterEq[i] = stack.isEmpty() ? n : stack.peek();
36 stack.push(i);
37 }
38 for (int i = 0; i < n; i++) {
39 sum += (long) arr[i] * (i - prevGreater[i]) * (nextGreaterEq[i] - i);
40 }
41
42 return (int) sum;
43 }
44}