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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2

Input: arr = [11,81,94,43,3]
Output: 444

Solution

Method 1 - Monotonic Increasing Stack

How Can Monotonic Stack Be Applied to This Problem?

Consider the element 3 in the array:

1
2

arr = [2, 9, 7, 8, 3, 4, 6, 1]
                   ^

The nearest smaller elements to the left (NSL) and right (NSR) (OR previous less element (PLE) and next less element(NLE)) of 3 are 2 and 1, respectively. The distance between 3 and its NSL 2 is 4, and the distance between 3 and its NSR 1 is 3.

The distance between 3 and its NSL 2 is 4. The distance between 3 and its NSR 1 is 3.

How Many Subarrays with 3 Being Its Minimum Value?

The answer is 4*3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

9 7 8 3 
9 7 8 3 4 
9 7 8 3 4 6 
7 8 3 
7 8 3 4 
7 8 3 4 6 
8 3 
8 3 4 
8 3 4 6 
3 
3 4 
3 4 6

How Much the Element 3 Contributes to the Final Answer?

It is 3*(4*3).

Algorithm

  • Denote by left[i] the distance between element A[i] and its NSL.
  • Denote by right[i] the distance between element A[i] and its NSR.
  • The final answer is, sum(arr[i]*left[i]*right[i] ) Here is the detailed approach:
  1. Monotonic Stack with Contribution Calculation:
    • Use a monotonic stack to track previous and next smaller elements for each element.
    • Compute how many subarrays in which each element is the minimum element.
    • Maintain two arrays, left and right, where left[i] indicates the number of contiguous subarrays ending at arr[i] in which arr[i] is the minimum, and right[i] indicates the number of contiguous subarrays starting at arr[i] in which arr[i] is the minimum.
    • The product of left[i] and right[i] gives the count of contexts where arr[i] is the minimum.
  2. Sum Calculation:
    • Calculate the sum of the contributions of all elements being the minimum in their respective subarrays and take modulo 10^9 + 7 to handle large numbers.

We have already seen following problems:

We also used it in Largest Rectangle in Histogram.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;
        int n = arr.length;
        
        Stack<Integer> stack = new Stack<>();
        int[] left = new int[n];
        int[] right = new int[n];
        
        // Fill left array
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        
        // Clear the stack for re-use
        stack.clear();
        
        // Fill right array
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
            stack.push(i);
        }
        
        // Calculate the result
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = (ans + (long) arr[i] * left[i] * right[i]) % MOD;
        }
        
        return (int) ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        
        stack = []
        left = [0] * n
        right = [0] * n
        
        # Fill left array
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            left[i] = i + 1 if not stack else i - stack[-1]
            stack.append(i)
        
        stack.clear()
        
        # Fill right array
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            right[i] = n - i if not stack else stack[-1] - i
            stack.append(i)
        
        # Calculate the result
        ans = 0
        for i in range(n):
            ans = (ans + arr[i] * left[i] * right[i]) % MOD
        
        return ans

Complexity

  • ⏰ Time complexity: O(n) for traversing the entire array and handling stack operations.
  • 🧺 Space complexity: O(n) for storing left, right, and the stack.

Method 2 - DP and Monotonic Stack

Using a monotonic increasing stack to store indices:

  • dp[i + 1]: Stores the sum of minimums of all subarrays ending with arr[i]
  • dp[i + 1] = dp[prev + 1] + (i - prev) * arr[i], where prev is the index of the previous smaller element, and as we are using monotonous increasing stack stack.peek()

For eg. for arr = [3, 1, 2, 4, 3], when i = 4, all subarrays end with arr[4] (which is 3):

  • [3]
  • [4, 3]
  • [2, 4, 3]
  • [1, 2, 4, 3]
  • [3, 1, 2, 4, 3]

Here, stack.peek() = 2 and arr[2] = 2.

For the first two subarrays [3] and [4, 3], the sum of minimum is (i - stack.peek()) * arr[i] = 6.

For the last three subarrays [2, 4, 3], [1, 2, 4, 3], [3, 1, 2, 4, 3], as they all contain a 2 which is less than 3, the sum of minimum is dp[stack.peek() + 1] = 4.

Thus, dp[i + 1] = 4 + 6 = 10.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int sumSubarrayMins(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int[] dp = new int[arr.length + 1];
        stack.push(-1);
        int result = 0;
        int MOD = (int) 1e9 + 7;
        
        for (int i = 0; i < arr.length; i++) {
            while (stack.peek() != -1 && arr[i] <= arr[stack.peek()]) {
                stack.pop();
            }
            dp[i + 1] = (dp[stack.peek() + 1] + (i - stack.peek()) * arr[i]) % MOD;
            stack.push(i);
            result = (result + dp[i + 1]) % MOD;
        }
        
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        stack = []
        dp = [0] * (len(arr) + 1)
        stack.append(-1)
        result = 0
        MOD = 10**9 + 7
        
        for i in range(len(arr)):
            while stack[-1] != -1 and arr[i] <= arr[stack[-1]]:
                stack.pop()
            dp[i + 1] = (dp[stack[-1] + 1] + (i - stack[-1]) * arr[i]) % MOD
            stack.append(i)
            result = (result + dp[i + 1]) % MOD
        
        return result

Complexity

  • ⏰ Time complexity: O(n) for iterating through the array and handling stack operations.
  • 🧺 Space complexity: O(n) for storing the dp array and stack.