907. Sum of Subarray Minimums

Problem Statement

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.

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

Intuition

Approach:
Brute:
In N^2 generate all sub-arrays , Then Take one more N to find min in arrays
N^3

Optimal
Use stack

Basically find the ith element is min till what range in left and right
Let
arr = 3 1 2 4
lef = 1 2 1 1 
rig = 1 3 2 1

Now, arr*left*right is answer  

Links

https://leetcode.com/problems/sum-of-subarray-minimums/description/

Video Links

Approach 1:

C++

class Solution {
public:

    int sumSubarrayMins(vector<int>& arr) {
        int n= arr.size();
        vector<int> left(n),right(n);
        stack<pair<int,int>>s,s2;

        for(int i=0;i<n;i++){
            int count=1;
            while(!s.empty() and s.top().first > arr[i]){
                count+=s.top().second;
                s.pop();
            }
            s.push({arr[i],count});
            left[i]=count;
        }

        for(int i=n-1;i>=0;i--){
            int count=1;
            while(!s2.empty() and s2.top().first >= arr[i]){
                count+=s2.top().second;
                s2.pop();
            }
            s2.push({arr[i],count});
            right[i]=count;
        }

        long long int sum=0,mod=1e9+7;

        for (int i = 0; i < n; i++){
            sum=(sum+(long long int)arr[i]*left[i]*right[i])%mod;
        }

        return sum;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems