AlgoViz
HomeStack

Sum of Subarray Ranges

Medium

Sum of maxima minus sum of minima

Problem

Return the sum over all subarrays of (max - min) of the subarray.

In simple words

Range of a subarray is max minus min; sum those, using monotonic stacks for max and min contributions.

The idea

The range of a subarray is its max minus its min, and sums distribute, so the answer is (sum of all subarray maxima) − (sum of all subarray minima). Each half is the contribution-counting problem above, run with the comparison flipped.

The trick

  • Two monotonic-stack passes, then a subtraction.
  • Apply the same tie-breaking discipline in both passes.
1
3
3
0
1
2

Step 1 of 8. Brute force: for every subarray, add (max − min) to the total. Values: 1, 3, 3.

1/8
Brute force
timeO(n²)spaceO(1)

Range of every subarray.

1for (let i = 0; i < n; i++) {2  let mn = Infinity, mx = -Infinity;3  for (let j = i; j < n; j++) { mn = Math.min(mn, nums[j]); mx = Math.max(mx, nums[j]); total += mx - mn; }4}

Input

array
[1, 3, 3]

Output

total
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 3]
Output:
4
Explanation:
Sum of (max-min) over all subarrays → 4.

Example 2

Input:
nums = [1, 3, 3]
Output:
4
Explanation:
Ranges add up to 4.

Example 3

Input:
nums = [4, -2, -3, 4, 1]
Output:
59
Explanation:
Bigger spreads → 59.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.