Description Link to heading

2104. Sum of Subarray Ranges (Medium) You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Example 2:

Input: nums = [1,3,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[3], range = 3 - 3 = 0
[3], range = 3 - 3 = 0
[1,3], range = 3 - 1 = 2
[3,3], range = 3 - 3 = 0
[1,3,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Example 3:

Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.

Constraints:

  • 1 <= nums.length <= 1000
  • -10⁹ <= nums[i] <= 10⁹

Follow-up: Could you find a solution with O(n) time complexity?

Solution Link to heading

The brute force approach, that is, enumerating the left endpoint and then enumerating the right endpoint in the sub-loop, identifies the maximum and minimum values in the subarray, entailing a time complexity of $O(n^2)$.

The outcome this problem seeks can be translated into the summation of the maximum values of all subarrays subtracted by the summation of the minimum values of all subarrays.

The summation of the maximum values of all subarrays is denoted as $sum_{max} = \sum\limits_{i=0}^{n-1} nums[i] * cnt_i$, where $cnt_i$ represents the quantity of subarrays in which nums[i] is the maximum value. At this point, the problem has been transformed into the task 795. Number of Subarrays with Bounded Maximum (Medium).

The summation of the minimum values of all subarrays is denoted as $sum_{min} = \sum\limits_{i=0}^{n-1} nums[i] *cnt_i$, where in this case $cnt_i$ is the number of subarrays in which nums[i] is the minimum value.

Code Link to heading 

class Solution {
  public:
    long long subArrayRanges(vector<int> &nums) {
        stack<int> stk;
        int n = nums.size();
        long sum_max = 0;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[i] > nums[stk.top()]) {
                int len1 = i - stk.top();
                int idx = stk.top();
                long val = nums[idx];
                stk.pop();
                int len2 = stk.empty() ? idx + 1 : idx - stk.top();
                sum_max += val * len1 * len2;
            }
            stk.push(i);
        }
        while (!stk.empty()) {
            int idx = stk.top();
            int len1 = n - idx;
            long val = nums[idx];
            stk.pop();
            int len2 = stk.empty() ? idx + 1 : idx - stk.top();
            sum_max += val * len1 * len2;
        }
        long sum_min = 0;
        stack<int> stk_min;
        for (int i = 0; i < n; ++i) {
            while (!stk_min.empty() && nums[i] < nums[stk_min.top()]) {
                int idx = stk_min.top();
                int len1 = i - idx;
                long val = nums[idx];
                stk_min.pop();
                int len2 = stk_min.empty() ? idx + 1 : idx - stk_min.top();
                sum_min += val * len1 * len2;
            }
            stk_min.push(i);
        }
        while (!stk_min.empty()) {
            int idx = stk_min.top();
            int len1 = n - idx;
            long val = nums[idx];
            stk_min.pop();
            int len2 = stk_min.empty() ? idx + 1 : idx - stk_min.top();
            sum_min += val * len1 * len2;
        }
        return sum_max - sum_min;
    }
};