Sum of Subarray Minimums — LeetCode 907 Python Solution
MediumStackArrayDynamic ProgrammingMonotonic Stack
- Problem
- #907
- Pattern
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the length of the array arr auxiliary |
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
LeetCode 85Maximal RectangleHardLeetCode 975Odd Even JumpHardLeetCode 1130Minimum Cost Tree From Leaf ValuesMediumLeetCode 1504Count Submatrices With All OnesMediumLeetCode 1526Minimum Number of Increments on Subarrays to Form a Target ArrayHardLeetCode 2617Minimum Number of Visited Cells in a GridHard
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.