< Back 907. Sum of Subarray Minimums Pretty difficult question, actually. We use a monotonically increasing stack to keep track of minimum values we encounter in each subarray, but determining how to find the number of subarrays a particular minimum applies to is pretty difficult. What we have to realize is that, given some range, l and r, the number of subarrays that the minimum value applies to is: (m - l) * (r - m) where m is in the index of the current minimum, l is the index of the previous minimum, and r is the index of the next minimum. To determine the contribution of the current minimum to the answer: arr[m] * (m - l) * (r - m) So we traverse the array from left to right, and maintain a monotonically increasing stack. When we need to manage the monotonically increasing stack, we pop off a value, known as the middle. We calculate l, the top of the stack and most recent minimum - otherwise -1 if the stack is empty. We calculate the count and contribution and add it to the answer for the current minimum. We then push the new minimum to the stack. We make sure to continue to process the stack and array until i == len(arr) - once i == len(arr), we need to continue to pop values from the stack until all minimums are processed. The solution is as follows: class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: stack = [] n, ans = len(arr), 0 for i in range(n + 1): while stack and (i == n or arr[stack[-1]] >= arr[i]): m = stack.pop() l = -1 if not stack else stack[-1] r = i ans += arr[m] * (m - l) * (r - m) stack.append(i) return ans % ((10**9) + 7) _ Time Complexity: O(n) - We inspect all elements in the array once. _ Space Complexity: O(n) - We maintain a monotonically increasing stack.