LeetCode Solutions Blog

Sum of Subarray Minimums

Number: 943

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers, compute the sum of the minimum values of every contiguous subarray. Since the result can be large, return the answer modulo 10^9 + 7.

Key Insights

Leverage a monotonic stack to determine the span over which an element is the minimum.
For each element, compute its "left" span (number of subarrays ending at the element where it is the minimum) and "right" span (number of subarrays starting at the element where it remains the minimum).
The contribution of an element is its value multiplied by its left and right spans.
Use modular arithmetic to handle large numbers.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The approach involves two passes using a monotonic stack. In the first pass, for each element, we count how many contiguous elements on the left (including the current one) are greater than (or equal, with a twist for handling duplicates) this element; this gives the left span. In the second pass, we do a similar traversal from the right to obtain the right span, ensuring that while moving right the criteria for maintaining the minimum includes strict comparisons in order to correctly handle duplicates. Finally, the element's overall contribution is the product of its value, its left span, and its right span. Summing up these contributions for all elements yields the answer modulo 10^9 + 7.

Code Solutions

# Python solution with detailed comments
class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10**9 + 7  # modulo value
        n = len(arr)
        left = [0] * n    # stores the number of contiguous subarrays ending at i where arr[i] is the minimum
        right = [0] * n   # stores the number of contiguous subarrays starting at i where arr[i] is the minimum
        
        stack = []
        # Calculate left spans
        for i in range(n):
            count = 1  # each element stands as a subarray itself
            # Pop while top element is greater than arr[i]
            while stack and arr[stack[-1][0]] > arr[i]:
                count += stack.pop()[1]
            stack.append((i, count))
            left[i] = count
        
        stack = []
        # Calculate right spans by iterating from right to left
        for i in range(n - 1, -1, -1):
            count = 1
            # Use >= here for the right side to correctly handle duplicates
            while stack and arr[stack[-1][0]] >= arr[i]:
                count += stack.pop()[1]
            stack.append((i, count))
            right[i] = count
        
        total = 0
        # Combine the contributions of each element
        for i in range(n):
            total = (total + arr[i] * left[i] * right[i]) % MOD
        return total