Sum of Subarray Ranges

Medium Monotonic Stack Monotonic Stack Original on LeetCode

Reported atAmazonD. E. Shaw

Sum of Subarray Ranges is a medium monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (contribution with monotonic stacks), runs in O(n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (every subarray, scan it) up.

Problem

You are given an integer array nums. The range of a subarray is the difference between its largest and its smallest element.

Return the sum of the ranges of all non-empty contiguous subarrays of nums.

Examples

Example 1

Input
nums = [2, 5, 1]
Output
11
Why
The ranges are 0, 0, 0 for the single elements, 3 for [2,5], 4 for [5,1] and 4 for [2,5,1]; 3 + 4 + 4 = 11.

Example 2

Input
nums = [3, 3, 3]
Output
0
Why
Every subarray has equal largest and smallest values.

Example 3

Input
nums = [-2, 4]
Output
6
Why
Only [-2, 4] has a non-zero range: 4 - (-2) = 6.

Constraints

  • 1 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9
  • The answer fits in a 64-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (every subarray, scan it)O(n³)O(1)
Better (extend each start with running max and min)O(n²)O(1)
Optimal (contribution with monotonic stacks)O(n)O(n)

1Brute force (every subarray, scan it)

TimeO(n³)O(n²) subarrays, each scanned in O(n).
SpaceO(1)Only a few counters.

Enumerate every pair of ends (i, j) and scan the subarray between them to find its largest and smallest value. Add their difference to the total.

  1. For each i, for each j >= i: scan nums[i..j] for max and min.
  2. Add max - min to the total.
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int max = nums[i], min = nums[i];
                for (int k = i; k <= j; k++) {
                    max = Math.max(max, nums[k]);
                    min = Math.min(min, nums[k]);
                }
                total += (long) max - min;
            }
        }
        return total;
    }
}

2Better (extend each start with running max and min)

TimeO(n²)Each of the O(n²) subarrays is handled in O(1).
SpaceO(1)Only the running values.

Fix the left end i and move the right end j forward. The maximum and minimum of nums[i..j] follow from those of nums[i..j-1] with one comparison each, so no inner scan is needed.

  1. For each i: max = min = nums[i].
  2. For each j from i to n - 1: update max and min with nums[j], add max - min.
class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long total = 0;
        for (int i = 0; i < n; i++) {
            int max = nums[i], min = nums[i];
            for (int j = i; j < n; j++) {
                max = Math.max(max, nums[j]);
                min = Math.min(min, nums[j]);
                total += (long) max - min;
            }
        }
        return total;
    }
}

3Optimal (contribution with monotonic stacks)

TimeO(n)Each index is pushed and popped once per scan, and there are two scans.
SpaceO(n)The stack can hold all n indices.

Split the answer into the sum of subarray maximums minus the sum of subarray minimums. nums[i] is the maximum of exactly (i - left) · (right - i) subarrays, where left is the previous index with a value >= nums[i] and right the next index with a value > nums[i] (the asymmetric tie rule counts each subarray once). A decreasing stack finds both neighbours: when an index is popped, the index that pops it is right and the index below it is left. The minimum side is the same with the comparison flipped.

  1. sumMax: scan i from 0 to n (i == n acts as +infinity). While the stack is not empty and (i == n or nums[top] < nums[i]): pop mid, left = new top or -1, add nums[mid] · (mid - left) · (i - mid). Push i.
  2. sumMin: same scan with (i == n or nums[top] > nums[i]).
  3. Return sumMax - sumMin.
class Solution {
    public long subArrayRanges(int[] nums) {
        return sumOf(nums, true) - sumOf(nums, false);
    }

    private long sumOf(int[] nums, boolean wantMax) {
        int n = nums.length;
        long sum = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() && (i == n || (wantMax ? nums[stack.peek()] < nums[i] : nums[stack.peek()] > nums[i]))) {
                int mid = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                sum += (long) nums[mid] * (mid - left) * (i - mid);
            }
            stack.push(i);
        }
        return sum;
    }
}

Edge cases to test

  • A single element: the answer is 0
  • Equal values next to each other (ties must not be counted twice in the stack method)
  • Strictly increasing or strictly decreasing arrays
  • Values near ±10^9: the sum needs 64-bit integers

Hints

Hint 1

The range of one subarray is its maximum minus its minimum, so the total is (sum of all subarray maximums) - (sum of all subarray minimums).

Hint 2

If you fix the left end and extend to the right, the running max and min update in O(1) per step.

Hint 3

For the O(n) solution, count for each nums[i] in how many subarrays it is the maximum: that is (distance to the previous larger element) × (distance to the next larger element). Monotonic stacks find those neighbours.

FAQ

What is the best time complexity for Sum of Subarray Ranges?

Optimal (contribution with monotonic stacks) runs in O(n) time and O(n) extra space. Each index is pushed and popped once per scan, and there are two scans.

Which pattern does Sum of Subarray Ranges use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Sum of Subarray Ranges?

Yes. Brute force (every subarray, scan it) takes O(n³) time and O(1) space. Enumerate every pair of ends (i, j) and scan the subarray between them to find its largest and smallest value.

Which edge cases should I test for Sum of Subarray Ranges?

A single element: the answer is 0; Equal values next to each other (ties must not be counted twice in the stack method); Strictly increasing or strictly decreasing arrays; Values near ±10^9: the sum needs 64-bit integers.