What pattern does Sum of Subarray Minimums use?

The Pattern: Monotonic Stack (Counting Subarray Contributions) The Heuristic: When a problem requires counting subarrays constrained by minimum or maximum values, use monotonic stacks to find the nearest smaller or larger elements on both sides, enabling O(n) computation of each element's contribution.

Sum of Subarray Minimums — Monotonic Stack

Q: What is the time complexity of Sum of Subarray Minimums?

O(n). Each element is pushed and popped at most once in each monotonic stack pass, resulting in linear time complexity.

Problem

Given an array of integers arr, return the sum of the minimum value of every subarray of arr modulo 10^9 + 7.

1 ≤ arr.length ≤ 3 * 10⁴
1 ≤ arr[i] ≤ 3 * 10⁴

Example

Input: arr = [3,1,2,4]

Output: 17

The subarrays of arr are: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. The minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1 respectively. Summing these gives 17. The algorithm uses two monotonic stacks to find, for each element, how many subarrays it is the minimum of by counting distances to previous less and next less elements. This allows calculating the total contribution of each element efficiently.

Approach

Straightforward Solution

A brute-force approach enumerates all subarrays and finds their minimums, resulting in O(n^2) or worse time complexity, which is infeasible for large arrays.

Core Observation

Each element in the array contributes to the sum as the minimum of a certain number of subarrays. The total contribution of an element equals its value multiplied by the count of subarrays where it is the minimum. To count these subarrays efficiently, one must find the distance to the previous less element and the next less element for each position.

Path to Optimal

Preview

The key insight is to use monotonic stacks to find, for each element, the nearest smaller element on the left and right. These boundaries define the range of subarrays where the current element is the minimum…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two passes with monotonic stacks: one from left to right to find distances to previous less elements, and one from right to left to find distances to next less elements. Then, accumulate the sum of arr[i] * left[i] * right[i] modulo 10^9 + 7…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is pushed and popped at most once in each monotonic stack pass, resulting in linear time complexity.

Space

O(n)

Auxiliary arrays left and right store distances for each element, and the stacks hold indices up to n elements, leading to O(n) auxiliary space.

Solution

Python

1class Solution:
  def sumSubarrayMins(self, arr: list[int]) -> int:
      mod = 10**9 + 7
      n = len(arr)
5
      left = [0] * n
      right = [0] * n
      stack = []
9
      for i in range(n):
          while stack and arr[stack[-1]] > arr[i]:
              stack.pop()
13
          if stack:
              left[i] = i - stack[-1]
          else:
              left[i] = i + 1
18
          stack.append(i)
20
      stack = []
22
      for i in range(n - 1, -1, -1):
          while stack and arr[stack[-1]] >= arr[i]:
              stack.pop()
26
          if stack:
              right[i] = stack[-1] - i
          else:
              right[i] = n - i
31
          stack.append(i)
33
      ans = 0
35
      for i in range(n):
          ans += arr[i] * left[i] * right[i]
          ans %= mod
39
      return ans

Step-by-Step Solution

1

Compute Distances to Previous Less Elements Using Monotonic Stack

3mod = 10**9 + 7
4n = len(arr)
6left = [0] * n
7right = [0] * n
8stack = []
10for i in range(n):
11    while stack and arr[stack[-1]] > arr[i]:
12        stack.pop()
14    if stack:
15        left[i] = i - stack[-1]
16    else:
17        left[i] = i + 1
19    stack.append(i)

Objective

To find, for each element, how many contiguous elements to the left are greater, defining the left boundary of subarrays where it is minimum.

Key Insight

A monotonic increasing stack maintains indices of elements in ascending order. For each new element, popping from the stack removes elements greater than the current one, revealing the nearest smaller element to the left. The distance from this smaller element to the current index defines how many subarrays can start to the left with the current element as minimum. This approach efficiently computes left boundaries in a single pass.

Interview Quick-Check

Core Logic

Use a monotonic increasing stack to find the nearest smaller element on the left for each index, enabling O(n) computation of left distances.

State & Boundaries

If no smaller element exists to the left, the distance is the index plus one, representing subarrays starting at the beginning.

Common Pitfalls & Bugs

Using a strict '>' comparison ensures correct handling of duplicates and prevents counting subarrays multiple times.

2

Compute Distances to Next Less Elements Using Monotonic Stack

To find, for each element, how many contiguous elements to the right are greater or equal, defining the right boundary of subarrays where it is minimum.

3

Accumulate Total Sum of Subarray Minimums Using Precomputed Distances

To calculate the total sum by multiplying each element's value by the count of subarrays where it is minimum and summing modulo 10^9 + 7.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 11 Critical

while stack and arr[stack[-1]] > arr[i]:

Pop indices from stack while top element is greater than current element.

This popping condition ensures the stack top always points to the nearest smaller element to the left, which is essential for correctly counting subarrays where the current element is minimum.

Line 24 Critical

while stack and arr[stack[-1]] >= arr[i]:

Pop indices from stack while top element is greater or equal to current element.

This condition ensures that the stack top always points to the nearest smaller element to the right, which is critical for counting subarrays without double counting when duplicates exist.

Line 37 Critical

ans += arr[i] * left[i] * right[i]

Add the contribution of the current element to the answer.

This multiplication and addition is the core calculation that transforms the problem from enumerating subarrays to summing contributions efficiently, enabling O(n) time complexity.

Full line-by-line criticality + rationale for all 27 lines available on Pro.

Test Your Understanding

Why does multiplying the distances to the previous less and next less elements give the count of subarrays where an element is the minimum?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sum of Subarray Minimums from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sum of Subarray Minimums drill

or drill a free problem

1	`class Solution:`
2	`def sumSubarrayMins(self, arr: list[int]) -> int:`
3	`mod = 10**9 + 7`
4	`n = len(arr)`
5
6	`left = [0] * n`
7	`right = [0] * n`
8	`stack = []`
9
10	`for i in range(n):`
11	`while stack and arr[stack[-1]] > arr[i]:`
12	`stack.pop()`
13
14	`if stack:`
15	`left[i] = i - stack[-1]`
16	`else:`
17	`left[i] = i + 1`
18
19	`stack.append(i)`
20
21	`stack = []`
22
23	`for i in range(n - 1, -1, -1):`
24	`while stack and arr[stack[-1]] >= arr[i]:`
25	`stack.pop()`
26
27	`if stack:`
28	`right[i] = stack[-1] - i`
29	`else:`
30	`right[i] = n - i`
31
32	`stack.append(i)`
33
34	`ans = 0`
35
36	`for i in range(n):`
37	`ans += arr[i] * left[i] * right[i]`
38	`ans %= mod`
39
40	`return ans`

3	`mod = 10**9 + 7`
4	`n = len(arr)`
6	`left = [0] * n`
7	`right = [0] * n`
8	`stack = []`
10	`for i in range(n):`
11	`while stack and arr[stack[-1]] > arr[i]:`
12	`stack.pop()`
14	`if stack:`
15	`left[i] = i - stack[-1]`
16	`else:`
17	`left[i] = i + 1`
19	`stack.append(i)`