Brute Force Solution

The most straightforward approach is to generate all possible subarrays and find the minimum element in each subarray. Then, sum up all the minimums.

def sum_of_minimums_brute_force(arr):
    total_sum = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            sub_array = arr[i:j+1]
            total_sum += min(sub_array)
    return total_sum

Time Complexity: O(n^3), where n is the length of the array. This is because we have nested loops to generate all subarrays (O(n^2)), and then we find the minimum of each subarray (O(n)).

Space Complexity: O(n), where n is the maximum size of a subarray that has to be held in memory.

Optimal Solution (Using Stack)

A more efficient approach utilizes a stack to find the nearest smaller elements to the left and right of each element in the array. This allows us to determine how many subarrays each element is the minimum for.

Here's how it works:

1. For each element arr[i], find the index left[i] of the nearest smaller element to the left.
2. For each element arr[i], find the index right[i] of the nearest smaller element to the right.
3. The number of subarrays where arr[i] is the minimum is (i - left[i]) * (right[i] - i). The sum of minimums is then the sum of arr[i] * (i - left[i]) * (right[i] - i) for all i.
4. Since the problem requests the answer modulo 10^9 + 7, perform modulus operations throughout the calculation.

def sum_of_minimums_optimal(arr):
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stack = []
    
    # Calculate left boundaries
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
        
    stack = []
    # Calculate right boundaries
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
        
    MOD = 10**9 + 7
    total_sum = 0
    
    for i in range(n):
        total_sum = (total_sum + arr[i] * (i - left[i]) * (right[i] - i)) % MOD
        
    return total_sum

Time Complexity: O(n), where n is the length of the array. We iterate through the array three times (once for left, once for right, and once for calculating the sum).

Space Complexity: O(n), for storing the left and right arrays and the stack.

Edge Cases

• Empty Array: If the input array is empty, the sum of minimums is 0. (Handled correctly as the loop will not be entered)
• Array with Duplicate Elements: The stack-based approach handles duplicate elements correctly by using '>=' when finding the right boundaries, ensuring that the current element is considered the minimum for subarrays extending to the right.
• Large Input Array: The code includes modulo operation to prevent integer overflow for large inputs.