907. Sum of Subarray Minimums

 

Sum of Subarray Minimums

Problem Description

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

Approach) Math

var sumSubarrayMins = function(A) {
    let mod=1000000007;
    let sum=0;
    for(let i=0; i<A.length; i++){
    	let left=i-1, right=i+1;
    	while(left>=0 && A[left]>=A[i]) left--;
    	while(right<A.length && A[right]>A[i]) right++;
    	sum=(sum+(right-i)*(i-left)*A[i]%mod)%mod;
    }
    return sum;
};

Note: To avoid double counting: A[left]>=A[i] and A[right]>A[i]

Approach) Monotonic Stack

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function (arr) {
  const MOD = Math.pow(10, 9) + 7;
  const n = arr.length;
  const stack = [];
  const leftBound = new Array(n).fill(-1);
  const rightBound = new Array(n).fill(n);

  for (let i = 0; i < n; i++) {
    while (stack.length && arr[i] < arr[stack[stack.length - 1]]) {
      const idx = stack.pop();
      rightBound[idx] = i;
    }
    if (stack.length > 0) leftBound[i] = stack[stack.length - 1];

    stack.push(i);
  }

  let ans = 0;
  for (let i = 0; i < n; i++) {
    const countLeft = i - leftBound[i];
    const countRight = rightBound[i] - i;
    const result = arr[i] * countLeft * countRight;

    ans += result;
  }

  return ans % MOD;
};

Approach) Stack

var sumSubarrayMins = function(arr) {
    
    M = 10**9+7
    stack = [-1]
    res = 0
    arr.push(0)
    
    for(let i2 = 0; i2 < arr.length; i2++){
        while(arr[i2] < arr[stack[stack.length -1]]){
            i = stack.pop()
            i1 = stack[stack.length-1]
            Left = i - i1
            Right = i2 -i
            res += (Left*Right*arr[i])
        };
        stack.push(i2)
    };
    
    return res%M
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 907. Sum of Subarray Minimums

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!