This problem can be solved using a stack data structure. Here is a step-by-step guide on how to solve it:

1. Initialize a stack. This stack will store the indices of the elements in the array. The bottom of the stack represents the current minimum.

2. Initialize two arrays, left and right, of the same length as the input array. These arrays will store the number of contiguous subarrays that can be formed to the left and right of each element in the array.

3. Iterate over the array from left to right. For each element, while the stack is not empty and the top of the stack is greater than the current element, pop the stack. The top of the stack now represents the first element to the left that is smaller than the current element. If the stack is empty, then the current element is the smallest so far. The number of contiguous subarrays that can be formed to the left of the current element is its index minus the index of the top of the stack.

4. Repeat the previous step but iterate from right to left to fill the right array.

5. Now that we have the left and right arrays, we can calculate the sum of the minimum of each subarray. Iterate over the array and for each element, add its value times the product of its corresponding values in the left and right arrays to the sum.

6. Finally, return the sum modulo 109 + 7 to get the result.

Here is a Python code snippet that implements the above steps:

```python
def sumSubarrayMins(arr):
MOD = 10**9 + 7
N = len(arr)

stack = []
prev = [0]*N
for i in range(N):
while stack and arr[i]

Question

This problem can be solved using a stack data structure. Here is a step-by-step guide on how to solve it:

1. Initialize a stack. This stack will store the indices of the elements in the array. The bottom of the stack represents the current minimum.

2. Initialize two arrays, left and right, of the same length as the input array. These arrays will store the number of contiguous subarrays that can be formed to the left and right of each element in the array.

3. Iterate over the array from left to right. For each element, while the stack is not empty and the top of the stack is greater than the current element, pop the stack. The top of the stack now represents the first element to the left that is smaller than the current element. If the stack is empty, then the current element is the smallest so far. The number of contiguous subarrays that can be formed to the left of the current element is its index minus the index of the top of the stack.

4. Repeat the previous step but iterate from right to left to fill the right array.

5. Now that we have the left and right arrays, we can calculate the sum of the minimum of each subarray. Iterate over the array and for each element, add its value times the product of its corresponding values in the left and right arrays to the sum.

6. Finally, return the sum modulo 109 + 7 to get the result.

Here is a Python code snippet that implements the above steps:

```python
def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    N = len(arr)

stack = []
    prev = [0]*N
    for i in range(N):
        while stack and arr[i] <= arr[stack[-1]]:
            stack.pop()
        prev[i] = stack[-1] if stack else -1
        stack.append(i)

stack = []
    next_ = [0]*N
    for k in range(N-1, -1, -1):
        while stack and arr[k] < arr[stack[-1]]:
            stack.pop()
        next_[k] = stack[-1] if stack else N
        stack.append(k)

return sum((i - prev[i]) * (next_[i] - i) * arr[i] for i in range(N)) % MOD
```

This function takes as input a list of integers and returns the sum of the minimum of each subarray modulo 109 + 7.

Knowee AI · Accepted Answer