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 109 + 7.
Example 1:
Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
Example 2:
Input: arr = [11,81,94,43,3] Output: 444
Constraints:
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104The monotonic stack approach leverages a stack data structure to efficiently determine the minimum element of every subarray. By maintaining indexes and utilizing their properties, we can efficiently compute the sum of all minimum values for the contiguous subarrays.
This C solution employs a monotonically increasing stack to determine the number of elements affected by each element of the array on either side, thus calculating its contribution to the final sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of auxiliary arrays and a stack.
A dynamic programming approach can also be adopted to tackle the given problem. This method involves calculating the contribution of each element to subarray minimums utilizing previously calculated results intelligently.
This C solution uses an array dp to compute subarray minimum sums progressively, allowing each integer's effect to persist cumulatively across numerous subarray possibilities.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n), where n is the length of the array. |
| Dynamic Programming Approach | Time Complexity: O(n) |
L9. Sum of Subarray Minimum | Stack and Queue Playlist • take U forward • 124,497 views views
Watch 9 more video solutions →Practice Sum of Subarray Minimums with our built-in code editor and test cases.
Practice on FleetCode