Algorithm

Problem Name: 907. Sum of Subarray Minimums

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

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

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
    
    private final static int MOD = 1000_000_007;
    
    public int sumSubarrayMins(int[] arr) {
        Stack < Integer> stack = new Stack<>();
        long sum = 0;
        for (int i = 0; i  < = arr.length; i++) {
            while (!stack.isEmpty() && (i == arr.length || arr[stack.peek()] >= arr[i])) {
                int minValue = stack.pop();
                int countOnLeft = stack.empty() ? -1 : stack.peek();
                int countOnRight = i;
                long totalCount = (minValue - countOnLeft) * (countOnRight - minValue) % MOD;
                sum = (sum + (totalCount * arr[minValue])) % MOD;
            }
            stack.push(i);
        }
        return (int) (sum);
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [3,1,2,4]

Output

x
–
+
cmd
17

#2 Code Example with Javascript Programming

Code - Javascript Programming


const sumSubarrayMins = function (arr) {
  const n = arr.length
  const mod = 1e9 + 7, stk = []
  const left = Array(n), right = Array(n)
  for(let i = 0; i <  n; i++) {
    left[i] = i + 1
    right[i] = n - i
  }
  let res = 0
  for(let i = 0; i  <  n; i++) {
    while(stk.length && arr[stk[stk.length - 1]] > arr[i]) {
      const idx = stk.pop()
      right[idx] = i - idx
    }
    if (stk.length) left[i] = i - stk[stk.length - 1]
    stk.push(i)
    
  }
  for(let i = 0; i  <  n; i++) {
    res = (res + arr[i] * left[i] * right[i]) % mod
  }
  
  return res
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [3,1,2,4]

Output

x
–
+
cmd
17

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def sumSubarrayMins(self, A):
        res, stack = 0, []  
        A = [float('-inf')] + A + [float('-inf')]
        for i, n in enumerate(A):
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                res += A[cur] * (i - cur) * (cur - stack[-1])
            stack.append(i)
        return res % (10 ** 9 + 7)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
arr = [11,81,94,43,3]

Output

x
–
+
cmd
444
Advertisements

Demonstration

Previous
#906 Leetcode Super Palindromes Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#908 Leetcode Smallest Range I Solution in C, C++, Java, JavaScript, Python, C# Leetcode