Sum of Subarray Minimums | Leetcode 907 | Stack Optimal Solution

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

Here’s the [Problem Link] to begin with.

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

Constraints:

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

Brute Force (Nested Loops)

Intuition and Approach

• Enumerate all subarrays starting at i and ending at j.
• Maintain running minimum for the current subarray and add it to the total.
• Take modulo each time to prevent overflow. This is simple and correct but not efficient for large n.

Code

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for i in range(0, n):
            mini = float("inf")
            for j in range(i, n):
                # Update running minimum for subarray arr[i..j]
                mini = min(mini, arr[j])
                # Add current subarray's minimum
                total = (total + mini) % (10**9 + 7)
        return total

Code Explanation

• For each starting index i, expand j to the right while tracking the current minimum mini.
• Each step contributes the current mini to the answer.
• Time grows quadratically due to all pairs (i, j).

Time and Space Complexity

• Precise: Time O(n^2), Space O(1).
• Simplified: Quadratic time; fine for small arrays, slow for large ones.

Conclusion

A great baseline for understanding the task, but not scalable.

Optimal (Monotonic Stack with PLE/NLE)

Intuition

View the sum as the sum of contributions of each element arr[i] as the minimum across all subarrays where it is the smallest. For any index i:

• Determine how many subarrays choose arr[i] as their minimum.
• Let ple[i] be the index of the Previous Less Element (strictly less) to the left of i; if none, use -1.
• Let nle[i] be the index of the Next Less Element (less or equal) to the right of i; if none, use n.
• Then the count of subarrays where arr[i] is minimum equals:
  • left = i − ple[i] choices for the left boundary
  • right = nle[i] − i choices for the right boundary
  • total subarrays contributed by i = left × right
• Contribution of arr[i] = arr[i] × left × right.

Why strict vs non-strict?

• To avoid double-counting equal elements, define PLE with “>” and NLE with “>=”. This breaks ties consistently: the “next less or equal” on the right ensures only one of equal elements takes ownership of a subarray.

Detailed Approach

• Compute PLE using a strictly increasing stack from left to right:
  • While top > arr[i], pop.
  • ple[i] = top index if exists, else -1.
• Compute NLE using a non-decreasing stack from right to left:
  • While top >= arr[i], pop.
  • nle[i] = top index if exists, else n.
• Sum contributions: arr[i] × (i − ple[i]) × (nle[i] − i), mod 1e9+7.

Code

class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10**9 + 7
        n = len(arr)
        stack = []
        ple = [-1] * n  # Previous Less Element index
        nle = [n] * n   # Next Less Element index

        # Previous Less Element (strictly less)
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            ple[i] = stack[-1] if stack else -1
            stack.append(i)

        # Reset stack
        stack = []

        # Next Less Element (less or equal)
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            nle[i] = stack[-1] if stack else n
            stack.append(i)

        # Calculate result by contribution
        result = 0
        for i in range(n):
            left = i - ple[i]
            right = nle[i] - i
            result = (result + arr[i] * left * right) % MOD

        return result

Code Explanation

• The first pass builds PLE using a monotonic increasing stack (values strictly increasing by indices): popping when a strictly greater value is found ensures ple[i] holds the nearest smaller element.
• The second pass builds NLE using a monotonic stack with “>=” popping to handle duplicates correctly and ensure a unique owner for tied values.
• The final loop aggregates each element’s contribution under modulo.

Time and Space Complexity

• Precise: Time O(n) (each index pushed/popped at most once per pass), Space O(n) for stacks and arrays.
• Simplified: Linear time and space; ideal for large inputs.

Conclusion

The monotonic stack solution transforms a quadratic enumeration into an elegant linear-time contribution sum. The choice of strict vs non-strict comparisons is crucial to avoid double-counting with duplicates.

When to Use Which

• Use the Brute Force method for learning and tiny inputs.
• Use the Monotonic Stack (PLE/NLE) method for production-grade efficiency with O(n) time.

Common Pitfalls and Tips

• Be mindful of tie-breaking: use “>” for PLE and “>=” for NLE.
• Always apply modulo at each accumulation to prevent overflow.
• Test with duplicates-heavy arrays (e.g., “) to validate tie-handling.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.