Medium

Sum of Subarray Ranges

LAB

Return the sum over every subarray of max(subarray) minus min(subarray).

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3
  ]
}

Output
4

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Run Q907 twice - once for minimums, once for maximums. The range is the difference.

Reveal reference solution +

pythonREFERENCE

def subArrayRanges(self, nums: List[int]) -> int:
    # Sum of max of all subarrays - Sum of min of all subarrays
    return self.sumSubarrayMaxs(nums) - self.sumSubarrayMins(nums)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗