2104. Sum of Subarray Ranges

Description

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
• -109 <= nums[i] <= 109

 

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

 

Solutions

Solution: Monotonic Stack

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const subArrayRanges = function (nums) {
  const compareSmall = (num, target) => num < target;
  const compareLarge = (num, target) => num > target;
  const sumRanges = (edge, compare) => {
    const stack = [];
    let result = 0;

    for (let index = 0; index <= nums.length; index++) {
      const num = nums[index] ?? edge;

      while (stack.length && compare(num, nums[stack.at(-1)])) {
        const previous = stack.pop();
        const start = stack.length ? stack.at(-1) : -1;
        const count = (index - previous) * (previous - start);

        result += nums[previous] * count;
      }
      stack.push(index);
    }
    return result;
  };
  const sumLargest = sumRanges(Number.MAX_SAFE_INTEGER, compareLarge);
  const sumSmallest = sumRanges(Number.MIN_SAFE_INTEGER, compareSmall);

  return sumLargest - sumSmallest;
};