NeetCode #374LC-907MediumStack
← Back to All Problems#374 · #907 · Sum of Subarray Minimums(子数组的最小值之和)
📌 Problem Statement & Constraints
Given an array of integers
arr, return the sum of min(b) over every contiguous subarray b, modulo 10^9 + 7. Constraints: 1 <= arr.length <= 3 * 10^4, 1 <= arr[i] <= 3 * 10^4.💡 Core Algorithmic Approaches
- Instead of enumerating subarrays, count how many subarrays have
arr[j]as their minimum. - Use a monotonic stack to find, for each
j, the previous smaller element's index and the next smaller element's index. - The count is
(j - prev_smaller) * (next_smaller - j), and the contribution isarr[j] * count. - Use
>=on one side and>on the other (here>=when popping) so that subarrays with equal minima are counted exactly once.
💻 Benchmark Python3 Implementation
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(arr)
st = []
total = 0
for i in range(n + 1):
# the sentinel i == n flushes the stack
while st and (i == n or arr[st[-1]] >= arr[i]):
j = st.pop()
left = st[-1] if st else -1 # previous strictly smaller
# arr[j] is the minimum for (j - left) * (i - j) subarrays
total += arr[j] * (j - left) * (i - j)
st.append(i)
return total % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
>in the pop condition: with duplicates, some subarrays would be counted twice and others not at all. One side must be non-strict, the other strict. - Computing the width as
i - left - 1: the count of left choices isj - leftand of right choices isi - j; multiplying those is correct, whereas the naive width formula is not. - Omitting the sentinel: elements left on the stack would never contribute.
- Enumerating all subarrays: O(n^2) with n = 3 * 10^4 is 4.5 * 10^8 operations.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.