MediumNo. 0907
Sum of Subarray Minimums — LeetCode 907 Python Solution
- Pattern
- Stack
- Topics
- Stack, Array, Dynamic Programming, Monotonic Stack
- Reading time
- 4 min
- Source
- leetcode.com
The 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 109 + 7.
Example
- 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].
Python solution
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)) % modComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)where n is the length of the array arr
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 907. Sum of Subarray Minimums is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0085 | Maximal Rectangle | Hard |
| 0975 | Odd Even Jump | Hard |
| 1130 | Minimum Cost Tree From Leaf Values | Medium |
| 1504 | Count Submatrices With All Ones | Medium |
| 1526 | Minimum Number of Increments on Subarrays to Form a Target Array | Hard |
| 2617 | Minimum Number of Visited Cells in a Grid | Hard |
Frequently asked questions
- How hard is LeetCode 907. Sum of Subarray Minimums?
LeetCode 907. Sum of Subarray Minimums is rated Medium on LeetCode.
- What is the time complexity of LeetCode 907. Sum of Subarray Minimums?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 907. Sum of Subarray Minimums?
The Python solution on this page uses O(n), where n is the length of the array arr auxiliary space.
- What topics does LeetCode 907. Sum of Subarray Minimums cover?
LeetCode 907. Sum of Subarray Minimums is tagged Stack, Array, Dynamic Programming and Monotonic Stack on LeetCode.