Brute Force Solution

The most straightforward approach is to generate all possible subarrays and then find the minimum element in each subarray. After finding the minimum, sum them up and return the result modulo 10^9 + 7.

Code:

def sum_of_minimums_brute_force(arr):
    MOD = 10**9 + 7
    total_sum = 0
    n = len(arr)

    for i in range(n):
        for j in range(i, n):
            sub_array = arr[i:j+1]
            total_sum += min(sub_array)
            total_sum %= MOD

    return total_sum

Time Complexity:

• O(n^3), where n is the length of the input array. This is because we have nested loops to generate all subarrays (O(n^2)), and finding the minimum in each subarray takes O(n) time.

Space Complexity:

• O(1), excluding the space used to store the subarray (which can be optimized).

Optimal Solution Using Stack

To optimize, we can use a stack to find the number of subarrays in which each element is the minimum. For each element arr[i], we need to find the left and right boundaries such that arr[i] is the minimum element in all subarrays within these boundaries.

Algorithm:

1. For each element arr[i], find the number of elements to its left and right that are greater than arr[i].
2. The number of subarrays in which arr[i] is the minimum is (left + 1) * (right + 1).
3. Multiply arr[i] with the number of subarrays it is the minimum in, and add it to the total sum.
4. Take modulo 10^9 + 7 at each step to avoid overflow.

Code:

def sum_of_minimums_optimal(arr):
    MOD = 10**9 + 7
    n = len(arr)
    stack = []
    left = [0] * n
    right = [0] * n

    # Calculate left boundaries
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i
        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] - i if stack else n - i - 1
        stack.append(i)

    total_sum = 0
    for i in range(n):
        total_sum += arr[i] * (left[i] + 1) * (right[i] + 1)
        total_sum %= MOD

    return total_sum

Time Complexity:

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

Space Complexity:

• O(n), where n is the length of the input array. We use two arrays, left and right, of size n to store the left and right boundaries for each element.

Edge Cases:

1. Empty array: The code should handle the case where the input array is empty. In this case, the sum of minimums is 0.
2. Array with one element: The code should correctly return the single element in the array.
3. Array with duplicate elements: The optimal solution correctly handles duplicate elements by using '>=' in the right boundary calculation, ensuring that the subarrays are counted correctly.