Sum Of Subarray Minimums - Leetcode Solution

Problem:

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.

Solution:

This problem can be solved using a stack-based algorithm that calculates the answer by computing the contribution of each element to the final answer. We use two stacks:

1. stack V: stores the unique values in the array arr.
2. stack W: stores the sum of the subarrays that end at or before each element in V.

The idea is to iterate over the array arr and calculate the sum of the subarray minimums for each element in arr. To do that, we take the following steps:

1. Pop the top element v of stack V and w of stack W if the current element in arr is smaller than v.
2. Let the current element in arr be a[i]. While the value v at the top of stack V is greater than a[i], pop it and add the corresponding sum w to the final answer. The subarrays that end at or before v also end at or before a[i], so we add w × (i - index_v) to the sum of min(b), where index_v is the index of v in arr.
3. Push a[i] to stack V and calculate the sum of the subarrays that end at or before a[i] by adding the sum of the subarrays that ended at or before the previous element in arr to a[i] × (i - index), where index is the index of the previous element in arr. Push the sum to stack W.

After iterating over all the elements in arr, the final answer is the sum of the values in stack W mod 10^9 + 7.

Pseudo code:

stack V, stack W for i in range(N): while V and arr[i] < V[-1]: V.pop() W.pop() if not V: index = -1 else: index = V[-1] s = (i - index) * arr[i] V.append(arr[i]) W.append((W[-1] if W else 0) + s) return sum(W) % (10 ** 9 + 7)

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input array arr, because we visit each element in arr exactly once and perform constant time operations for each element.

Space Complexity:

The space complexity of this solution is O(N), because we store each element in arr in stack V and we also store the sum of the subarrays that end at or before each element in arr in stack W.

1