Brute Force Solution

A naive approach would be to iterate through all possible subarrays, find the minimum element in each subarray, and sum up these minimums. This approach is straightforward but inefficient.

Algorithm

1. Iterate through all possible start indices i from 0 to n-1.
2. For each start index i, iterate through all possible end indices j from i to n-1.
3. For each subarray arr[i...j], find the minimum element.
4. Add the minimum element to the total sum.
5. Return the total sum modulo 10^9 + 7.

Code (Python)

def sum_of_minimums_brute_force(arr):
    n = len(arr)
    total_sum = 0
    for i in range(n):
        for j in range(i, n):
            min_val = arr[i]
            for k in range(i + 1, j + 1):
                min_val = min(min_val, arr[k])
            total_sum = (total_sum + min_val) % (10**9 + 7)
    return total_sum

Time Complexity

The time complexity of this brute-force approach is O(n^3), where n is the length of the input array. This is because we have three nested loops: the outer two loops to define the subarrays (O(n^2)), and the inner loop to find the minimum element in each subarray (O(n)).

Space Complexity

The space complexity is O(1), as we only use a constant amount of extra space.

Optimal Solution Using Stack

A more efficient approach involves using stacks to determine the left and right boundaries for each element in the array, where that element is the minimum.

Algorithm

1. For each element arr[i], find the number of subarrays where arr[i] is the minimum.
2. To do this, find the left boundary left[i] such that arr[i] is the minimum to the left and right boundary right[i] such that arr[i] is the minimum to the right.
3. Use stacks to efficiently compute left[i] and right[i] for each index i.
4. The number of subarrays in which arr[i] is the minimum is (i - left[i]) * (right[i] - i).
5. Sum up arr[i] * (i - left[i]) * (right[i] - i) for all i, taking the modulo 10^9 + 7.

Code (Python)

def sum_subarray_mins(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)
    
    total_sum = 0
    for i in range(n):
        total_sum = (total_sum + arr[i] * (i - left[i]) * (right[i] - i)) % (10**9 + 7)
        
    return total_sum

Time Complexity

The time complexity of this optimized approach is O(n), where n is the length of the input array. This is because we iterate through the array three times: once to calculate the left boundaries, once to calculate the right boundaries, and once to compute the final sum. Each iteration is O(n), and stack operations are O(1) on average.

Space Complexity

The space complexity is O(n), as we use two arrays, left and right, of size n to store the left and right boundaries for each element. We also use a stack, which, in the worst case, can contain all the elements of the array.

Edge Cases

• Empty Array: If the input array is empty, the sum of minimums should be 0.
• Array with One Element: If the array has only one element, the sum of minimums is the element itself.
• Array with Duplicate Elements: The algorithm correctly handles arrays with duplicate elements, considering each element's contribution to the sum based on its boundaries.