LC-2104 Medium LeetCode

2104. Sum of Subarray Ranges

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 60% Topics: Array, Stack, Monotonic Stack

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def subArrayRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        stk = []
        for i in xrange(len(nums)+1):
            x = nums[i] if i < len(nums) else float("inf")
            while stk and nums[stk[-1]] <= x:
                j = stk.pop()
                k = stk[-1] if stk else -1
                result += nums[j]*(j-k)*(i-j)
            stk.append(i)
        stk = []
        for i in xrange(len(nums)+1):
            x = nums[i] if i < len(nums) else float("-inf")
            while stk and nums[stk[-1]] >= x:
                j = stk.pop()
                k = stk[-1] if stk else -1
                result -= nums[j]*(j-k)*(i-j)
            stk.append(i)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT