☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Sum of Subarray Ranges

Medium TUF ID 972 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

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 contiguous, non-empty subarrays of nums.

Constraints: 1 ≤ n ≤ 1000 on LeetCode (the optimal method below handles 10^5 easily), -10^9 ≤ nums[i] ≤ 10^9. The answer can be far larger than an int, so it is returned as a long.

Example 1

nums   = [1, 2, 3]
answer = 4        // ranges: [1]=0 [2]=0 [3]=0 [1,2]=1 [2,3]=1 [1,2,3]=2

Example 2

nums   = [1, 3, 3]
answer = 4        // [1,3]=2, [3,3]=0, [1,3,3]=2, single elements give 0

Example 3

nums   = [4, -2, -3, 4, 1]
answer = 59

Approach 1: Brute force

Intuition. Do exactly what the statement says. A subarray is fixed by its start i and end j. For each of the n(n+1)/2 pairs, scan the elements between them to find the maximum and the minimum, then add the difference.

Algorithm.

  1. For every start i and every end j ≥ i:
  2. Scan nums[i..j], keeping the running maximum mx and minimum mn.
  3. Add mx - mn to the total.
static long bruteForce(int[] nums) {
    int n = nums.length;
    long total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int mx = nums[i], mn = nums[i];
            for (int k = i; k <= j; k++) {
                mx = Math.max(mx, nums[k]);
                mn = Math.min(mn, nums[k]);
            }
            total += (long) mx - mn;
        }
    }
    return total;
}

Complexity. Time O(n^3): O(n^2) subarrays, each scanned in O(n). Space O(1).

The subtraction is done as (long) mx - mn. With values in [-10^9, 10^9] the difference can reach 2 × 10^9, which is just beyond Integer.MAX_VALUE.

Approach 2: Better, extend the subarray one element at a time

Intuition. The brute force throws away work. The subarray nums[i..j+1] is nums[i..j] plus one element, so its maximum is max(previous maximum, nums[j+1]), and likewise for the minimum. If we fix the start and grow the end, we can maintain both in O(1) per step instead of rescanning.

Algorithm.

  1. For every start i, set mx = mn = nums[i].
  2. For every end j from i to n - 1: update mx and mn with nums[j], then add mx - mn.
static long better(int[] nums) {
    int n = nums.length;
    long total = 0;
    for (int i = 0; i < n; i++) {
        int mx = nums[i], mn = nums[i];
        for (int j = i; j < n; j++) {
            mx = Math.max(mx, nums[j]);
            mn = Math.min(mn, nums[j]);
            total += (long) mx - mn;              // long: max - min can reach 2 * 10^9
        }
    }
    return total;
}

Complexity. Time O(n^2), one constant-time update per subarray. Space O(1).

This is fast enough for the LeetCode limit of n = 1000 (half a million subarrays). It is not fast enough for n = 10^5, where there are 5 × 10^9 subarrays. To go further we have to stop thinking about subarrays one at a time.

Approach 3: Optimal, contribution of each element with monotonic stacks

Intuition. Split the sum in two:

sum over subarrays of (max - min) = (sum of subarray maximums) - (sum of subarray minimums)

Now flip the question. Instead of asking “what is the minimum of this subarray?”, ask “in how many subarrays is nums[i] the minimum?”. If that count is c[i], then nums[i] contributes nums[i] × c[i] to the sum of minimums, and

sum of minimums = Σ nums[i] × c[i]

How many subarrays have nums[i] as their minimum? Such a subarray must contain index i and must not reach any element smaller than nums[i]. Walk left from i until the first element smaller than nums[i]; the subarray may start anywhere in between, which gives left[i] choices. Do the same to the right for right[i] choices of end. Every start can be combined with every end, so c[i] = left[i] × right[i].

Ties need care. In [2, 2] the subarray [2, 2] has minimum 2, but it must be credited to only one of the two 2s. The code uses a strict comparison on one side and a non-strict one on the other:

With this rule a subarray whose minimum appears several times is credited to the leftmost copy only, so every subarray is counted exactly once.

Finding “the previous element ≤ x” and “the next element < x” for every index is the classic previous / next smaller element problem. A stack of indices whose values increase from bottom to top answers it in one pass: before pushing i, pop everything that cannot be the answer for i (anything greater, on the left pass); whatever is left on top is the answer. Each index is pushed and popped once, so each pass is linear.

The sum of maximums is the mirror image: flip every comparison.

Algorithm.

  1. Left pass for the minimum: for i = 0 .. n-1, pop while a[top] > a[i]; then left[i] = i - top, or i + 1 if the stack is empty. Push i.
  2. Right pass: for i = n-1 .. 0, pop while a[top] ≥ a[i]; then right = top - i, or n - i if empty. Add a[i] × left[i] × right. Push i.
  3. Repeat with the comparisons reversed to get the sum of maximums.
  4. Return sumOfMaximums - sumOfMinimums.
static long optimal(int[] nums) {
    return sumOfMaximums(nums) - sumOfMinimums(nums);
}

static long sumOfMinimums(int[] a) {
    int n = a.length;
    long total = 0;
    int[] left = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && a[st.peek()] > a[i]) st.pop();      // stop at previous element <= a[i]
        left[i] = st.isEmpty() ? i + 1 : i - st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && a[st.peek()] >= a[i]) st.pop();     // stop at next element < a[i]
        int right = st.isEmpty() ? n - i : st.peek() - i;
        total += (long) a[i] * left[i] * right;
        st.push(i);
    }
    return total;
}

static long sumOfMaximums(int[] a) {
    int n = a.length;
    long total = 0;
    int[] left = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && a[st.peek()] < a[i]) st.pop();      // stop at previous element >= a[i]
        left[i] = st.isEmpty() ? i + 1 : i - st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && a[st.peek()] <= a[i]) st.pop();     // stop at next element > a[i]
        int right = st.isEmpty() ? n - i : st.peek() - i;
        total += (long) a[i] * left[i] * right;
        st.push(i);
    }
    return total;
}

Dry run on nums = [1, 2, 3]:

i a[i] left / right (as max) max contribution left / right (as min) min contribution
0 1 1 / 1 1 1 / 3 3
1 2 2 / 1 4 1 / 2 4
2 3 3 / 1 9 1 / 1 3

Sum of maximums = 14 (the maximums of the six subarrays are 1, 2, 3, 2, 3, 3). Sum of minimums = 10 (1, 2, 3, 1, 2, 1). The answer is 14 - 10 = 4.

Read row i = 2 as a maximum: 3 is larger than everything to its left, so a subarray ending at index 2 may start at index 0, 1 or 2 (left = 3), and nothing lies to its right (right = 1). It is the maximum of three subarrays.

Complexity. Time O(n): four passes, and in each pass every index is pushed once and popped at most once. Space O(n) for the left array and the stack.

Why the products are computed as long. left[i] × right[i] can reach about n^2 / 4, which is 250 000 for n = 1000. Multiplied by a value near 10^9, a single contribution is around 2.5 × 10^14, far beyond int. The cast (long) a[i] * left[i] * right makes the whole product long from the first multiplication, because Java evaluates it left to right. Writing (long) (a[i] * left[i] * right) would multiply in int, overflow, and only then widen the wrong result.

Edge cases and pitfalls