Solution For Sum Of Subarray Minimums

Problem:

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 10^9 + 7.

Solution:

This problem can be solved using a stack-based algorithm that calculates the answer by computing the contribution of each element to the final answer. We use two stacks:

1. stack V: stores the unique values in the array arr.
2. stack W: stores the sum of the subarrays that end at or before each element in V.

The idea is to iterate over the array arr and calculate the sum of the subarray minimums for each element in arr. To do that, we take the following steps:

1. Pop the top element v of stack V and w of stack W if the current element in arr is smaller than v.
2. Let the current element in arr be a[i]. While the value v at the top of stack V is greater than a[i], pop it and add the corresponding sum w to the final answer. The subarrays that end at or before v also end at or before a[i], so we add w × (i – index_v) to the sum of min(b), where index_v is the index of v in arr.
3. Push a[i] to stack V and calculate the sum of the subarrays that end at or before a[i] by adding the sum of the subarrays that ended at or before the previous element in arr to a[i] × (i – index), where index is the index of the previous element in arr. Push the sum to stack W.

After iterating over all the elements in arr, the final answer is the sum of the values in stack W mod 10^9 + 7.

Pseudo code:

stack V, stack W
for i in range(N):
while V and arr[i] < V[-1]:
V.pop()
W.pop()
if not V:
index = -1
else:
index = V[-1] s = (i – index) * arr[i] V.append(arr[i])
W.append((W[-1] if W else 0) + s)
return sum(W) % (10 ** 9 + 7)

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input array arr, because we visit each element in arr exactly once and perform constant time operations for each element.

Space Complexity:

The space complexity of this solution is O(N), because we store each element in arr in stack V and we also store the sum of the subarrays that end at or before each element in arr in stack W.

Step by Step Implementation For Sum Of Subarray Minimums

class Solution {
    public int sumSubarrayMins(int[] A) {
        // initialize prefix and suffix arrays
        int[] prefix = new int[A.length];
        int[] suffix = new int[A.length];
        
        // initialize current minimum to the first element in the array
        int currMin = A[0];
        
        // fill prefix array
        for (int i = 0; i < A.length; i++) {
            // update current minimum
            currMin = Math.min(currMin, A[i]);
            
            // update prefix array at index i
            prefix[i] = currMin;
        }
        
        // reset current minimum
        currMin = A[A.length - 1];
        
        // fill suffix array in reverse
        for (int i = A.length - 1; i >= 0; i--) {
            // update current minimum
            currMin = Math.min(currMin, A[i]);
            
            // update suffix array at index i
            suffix[i] = currMin;
        }
        
        // initialize sum
        int sum = 0;
        
        // calculate sum of subarray minimums
        for (int i = 0; i < A.length; i++) {
            sum += Math.min(prefix[i], suffix[i]);
        }
        
        return sum;
    }
}

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [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.
 

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

var sumOfSubarrayMins = function(A) {
    let totalSum = 0;
    
    for(let i = 0; i < A.length; i++){
        let min = A[i];
        
        for(let j = i; j < A.length; j++){
            min = Math.min(min, A[j]);
            totalSum += min;
        }
    }
    
    return totalSum;
};

class Solution {
public:
    int sumSubarrayMins(vector& A) {
        int MOD = 1e9+7;
        int n = A.size();
        stack s;
        vector left(n);
        for (int i = 0; i < n; ++i) {
            int count = 1;
            while (!s.empty() && s.top() > A[i]) {
                count += left[s.top()];
                s.pop();
            }
            left[i] = count;
            s.push(i);
        }
        while (!s.empty()) s.pop();
        vector right(n);
        for (int i = n-1; i >= 0; --i) {
            int count = 1;
            while (!s.empty() && s.top() >= A[i]) {
                count += right[s.top()];
                s.pop();
            }
            right[i] = count;
            s.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += A[i] * left[i] * right[i];
            ans %= MOD;
        }
        return ans;
    }
};

class Solution {
    public int SumSubarrayMins(int[] A) {
        
        // create a stack to keep track of the indices of the array
        Stack stack = new Stack();
        
        // create an array to store the results
        int[] result = new int[A.Length];
        
        // iterate through the array
        for(int i = 0; i < A.Length; i++){
            
            // while the stack is not empty and the current element is less than the element at the top of the stack
            while(stack.Count != 0 && A[i] < A[stack.Peek()]){
                
                // pop the element off the top of the stack
                int index = stack.Pop();
                
                // calculate the number of subarrays that have the element at the current index as the minimum
                int numSubarrays = i - index;
                
                // if the stack is empty, then all subarrays from the current index to the end of the array have the current element as the minimum
                if(stack.Count == 0)
                    numSubarrays = i + 1;
                // otherwise, the number of subarrays is the difference between the current index and the index of the element at the top of the stack
                else
                    numSubarrays = i - stack.Peek() - 1;
                
                // calculate the sum of subarray minimums and store it in the result array
                result[index] += A[index] * numSubarrays;
            }
            
            // push the current index onto the stack
            stack.Push(i);
        }
        
        // while the stack is not empty
        while(stack.Count != 0){
            
            // pop the element off the top of the stack
            int index = stack.Pop();
            
            // calculate the number of subarrays that have the element at the current index as the minimum
            int numSubarrays = A.Length - index;
            
            // if the stack is empty, then all subarrays from the current index to the end of the array have the current element as the minimum
            if(stack.Count == 0)
                numSubarrays = A.Length - index;
            // otherwise, the number of subarrays is the difference between the current index and the index of the element at the top of the stack
            else
                numSubarrays = A.Length - stack.Peek() - 1;
                
            // calculate the sum of subarray minimums and store it in the result array
            result[index] += A[index] * numSubarrays;
        }
        
        // return the sum of the result array
        return result.Sum();
    }
}