LC 2104

Solution to LeetCode 2104 Sum of Subarray Ranges

LeetCode 2104

Sum of Subarray Ranges (Medium) [link]

1] Brute Force Solution. Time complexity O(n^2).

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            MAX = -inf
            MIN = inf
            for j in range(i, len(nums)):
                MAX = max(nums[j], MAX)
                MIN = min(nums[j], MIN)
                ans += (MAX - MIN)
        return ans

2] Monotonic Stack. For each element, we calculate the number of times it is the max within a certain range, and the number of times it is the min within a certain range. Then the sum of all ranges of all possible subarray is “+sum(number of times it is the max within a certain range) - sum(number of times it is the min within a certain range)”.

$sumMin=∑_{i=0}^{n-1}(minRight[i]−i)×(i−minLeft[i])×nums[i]$

$sumMax=∑_{i=0}^{n-1}(maxRight[i]−i)×(i−maxLeft[i])×nums[i]$

Time complexity O(n).

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        minLeft, maxLeft = [0] * n, [0] * n
        minStack, maxStack = [], []
        for i, num in enumerate(nums):
            while minStack and nums[minStack[-1]] > num: # don't want to pop the tie because they are not min of each other
                minStack.pop()
            minLeft[i] = minStack[-1] if minStack else -1
            minStack.append(i)

            while maxStack and nums[maxStack[-1]] <= num: # pop the tie because they are not max of each other
                maxStack.pop()
            maxLeft[i] = maxStack[-1] if maxStack else -1
            maxStack.append(i)

        minRight, maxRight = [0] * n, [0] * n
        minStack, maxStack = [], []
        for i in range(n - 1, -1, -1):
            num = nums[i]
            while minStack and nums[minStack[-1]] >= num:
                minStack.pop()
            minRight[i] = minStack[-1] if minStack else n
            minStack.append(i)

            while maxStack and nums[maxStack[-1]] < num:
                maxStack.pop()
            maxRight[i] = maxStack[-1] if maxStack else n
            maxStack.append(i)

        sumMax, sumMin = 0, 0
        for i, num in enumerate(nums):
            sumMax += (maxRight[i] - i) * (i - maxLeft[i]) * num
            sumMin += (minRight[i] - i) * (i - minLeft[i]) * num
        return sumMax - sumMin

LeetCode 907