⚡Flashcard Drill➔
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

  1. Instead of enumerating subarrays, count how many subarrays have arr[j] as their minimum.
  2. Use a monotonic stack to find, for each j, the previous smaller element's index and the next smaller element's index.
  3. The count is (j - prev_smaller) * (next_smaller - j), and the contribution is arr[j] * count.
  4. 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 is j - left and of right choices is i - 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems