Sum of Subarray Minimums
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Sum of subarray minimums, Arrays, Subarray, Stack, Monotonic Stack, Time Complexity, Space Complexity, Optimization, Brute Force, Modular Arithmetic, complexity analysis, dynamic programming, subarray, combinatorics, monotonic stack, array traversal.
Sum of Subarray Minimums Given an array of integers arr, find the sum of min(b) for every contiguous subarray b of arr. Since the answer may be large, return the answer modulo 10^9 + 7. Input Specification: A single line containing space separated integers representing the array arr. Output Specification: Return a single integer, the sum of subarray minimums modulo 10^9 + 7. Constraints: 1 <= arr.length <= 3 10^4 1 <= arr[i] <= 3 10^4 Sample Test Case: Input: 3 1 2 4 Output: 17 Explanation: Subarrays and their minimums: [3]: 3 [1]: 1 [2]: 2 [4]: 4 [3,1]: 1 [1,2]: 1 [2,4]: 2 [3,1,2]: 1 [1,2,4]: 1 [3,1,2,4]: 1 Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17