< Back





2104. Sum of Subarray Ranges

Pretty similar to 907. Sum of Subarray Minimums.

What we have to realize is that, given some range, l and r, the number of subarrays that the minimum
or maximum value applies to is:

  (m - l) * (r - m)

where m is in the index of the current minimum or maximum, l is the index of the previous minimum
or maximum, and r is the index of the next minimum or maximum. To determine the contribution of the
current minimum or maximum to the answer:

  arr[m] * (m - l) * (r - m)

So we traverse the array from left to right, and maintain a monotonically increasing or decreasing
stack. When we need to manage the monotonically increasing or decreasing stack, we pop off a value,
known as the middle. We calculate l, the top of the stack and most recent minimum - otherwise -1 if
the stack is empty. We calculate the count and contribution and add it to the answer for the current
minimum or maximum. We then push the new minimum or maximum to the stack.

We make sure to continue to process the stack and array until r == len(arr) - once r == len(arr), we
need to continue to pop values from the stack until all minimums or maximums are processed.

The trick to this problem is we're asked to find:

  sum(ranges)

where a range is the difference between the minimum and maximum value for a given subarray.
Therefore we can define the problem as:

  sum(maximum_k - minimum_k) for some k where k is a subarray

Since we're processing all maximums and minimums of subarrays in k, we can break the problem down
further to:

  sum(maximums) - sum(minimums) for all k

So now we can just find all the maximums and minimums of subarrays and then calculate their
difference.

The solution is as follows:


  class Solution:
      def subArrayRanges(self, nums: List[int]) -> int:
          n, ans = len(nums), 0
          stack = []

          for r in range(n + 1):
              while stack and (r == n or nums[stack[-1]] >= nums[r]):
                  m = stack.pop()
                  l = -1 if not stack else stack[-1]
                  ans -= nums[m] * (m - l) * (r - m)

              stack.append(r)

          stack.clear()

          for r in range(n + 1):
              while stack and (r == n or nums[stack[-1]] <= nums[r]):
                  m = stack.pop()
                  l = -1 if not stack else stack[-1]
                  ans += nums[m] * (m - l) * (r - m)

              stack.append(r)

          return ans


_ Time Complexity:

  O(n) - We inspect all elements in the array twice.

_ Space Complexity:

  O(n) - We maintain two monotonic stacks.