Solution Explanation: Sum of Subarray Minimums

This problem asks to find the sum of the minimum values among all contiguous subarrays of a given array arr. A brute-force approach would have a time complexity of O(n^3), which is inefficient for large arrays. The optimal solution utilizes a monotonic stack to achieve a linear time complexity.

Algorithm:

The core idea is to efficiently determine, for each element arr[i], the number of subarrays where arr[i] is the minimum element. We can achieve this by finding:

1. left[i]: The index of the nearest element to the left of arr[i] that is strictly less than arr[i].
2. right[i]: The index of the nearest element to the right of arr[i] that is less than or equal to arr[i].

Once we have left[i] and right[i], the number of subarrays where arr[i] is the minimum is (i - left[i]) * (right[i] - i). The total sum is then calculated by summing up arr[i] * (i - left[i]) * (right[i] - i) for all i.

Monotonic Stack Implementation:

A monotonic stack (decreasing in this case) is used to efficiently find left[i] and right[i].

• Finding left[i]: We iterate through the array from left to right. The stack maintains indices of elements in decreasing order. When we encounter an element arr[i], we pop elements from the stack that are greater than or equal to arr[i]. The top element of the stack after popping is then left[i]. If the stack is empty, it means left[i] is -1 (no smaller element to the left).

• Finding right[i]: We iterate through the array from right to left. The stack maintains indices of elements in decreasing order. The process is similar to finding left[i], except we pop elements strictly greater than arr[i]. This ensures that we don't count overlapping subarrays when the minimum value repeats.

Time and Space Complexity:

• Time Complexity: O(n) - Each element is pushed and popped onto/off the stack at most once.
• Space Complexity: O(n) - The stack and the left and right arrays can store up to n elements in the worst case.

Code Explanation (Python):

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, v in enumerate(arr):
            while stk and arr[stk[-1]] >= v:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
 
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and arr[stk[-1]] > arr[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)
        mod = 10**9 + 7
        return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod
 

The code efficiently calculates left[i] and right[i] using monotonic stacks and then computes the final sum, handling modulo operations to prevent integer overflow. The other provided code examples in Java, C++, Go, TypeScript and Rust follow the same algorithmic approach, adapted to their respective syntax and data structures.