Sum of Subarray Sum Minimums

XXX. Sum of Subarray Minimums

Monotonic Stack

Dynamic Programming

Problem Statement:

Given an array arr, find the sum of the minimum element of every subarray of arr. As the answer may be large, return it modulo 109 + 7.

Algorithm:

The algorithm uses a monotonic increasing stack to efficiently calculate the contribution of each element as the minimum in all subarrays it belongs to:

1. Iterate through the array and include an additional iteration for cleanup after processing all elements.
2. Maintain a monotonic increasing stack where each element is smaller than the next. This ensures that the current element is the minimum for its subarrays.
3. For each element:
• If the current element is smaller than the top of the stack or we have processed all elements, calculate the contribution of the top element in all subarrays where it is the minimum.
• Pop the top element from the stack and calculate its contribution as:
• Number of subarrays where it is the minimum = (mid - leftBoundary) * (rightBoundary - mid).
• Multiply this count by the value of the element and add it to the result modulo 109 + 7.
• Push the current index onto the stack.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is pushed and popped from the stack once.
Space Complexity: O(n), for the stack used to store indices.

Java Implementation:

import java.util.*;

public class Solution {
    // Actually not that hardddd at allll
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1000000007;

        Stack stack = new Stack<>();
        long sumOfMinimums = 0;

        // Building monotonically increasing stack
        for (int i = 0; i <= arr.length; i++) {

            // When i reaches the array length, it is an indication that
            // all the elements have been processed, and the remaining
            // elements in the stack should now be popped out.
            while (!stack.empty() && (i == arr.length || arr[stack.peek()] >= arr[i])) {

                // Notice the sign ">=", This ensures that no contribution
                // is counted twice. rightBoundary takes equal or smaller 
                // elements into account while leftBoundary takes only the
                // strictly smaller elements into account

                int mid = stack.pop();
                int leftBoundary = stack.empty() ? -1 : stack.peek();
                int rightBoundary = i;

                // Count of subarrays where mid is the minimum element
                long count = (mid - leftBoundary) * (rightBoundary - mid) % MOD;

                sumOfMinimums += (count * arr[mid]) % MOD;
                sumOfMinimums %= MOD;
            }
            stack.push(i);
        }

        return (int) (sumOfMinimums);
    }
}