Sum of Subarray Minimums

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.

Q: 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.

Medium Stacks

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

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. By multiplying the distances to these boundaries, one obtains the count of subarrays where the element is minimum. Summing the contributions of all elements yields the final answer in O(n) time.

Optimal Approach

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. This approach achieves O(n) time and O(n) space complexity.

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.

Pattern Spotlight

Monotonic Stack (Counting Subarray Contributions)

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.

Solution

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

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.

Compute Distances to Next Less Elements Using Monotonic Stack

21stack = []
23for i in range(n - 1, -1, -1):
  while stack and arr[stack[-1]] >= arr[i]:
      stack.pop()
  if stack:
      right[i] = stack[-1] - i
  else:
      right[i] = n - i
  stack.append(i)

Objective

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.

Key Insight

A monotonic increasing stack is used again, but iterating from right to left. For each element, popping from the stack removes elements greater or equal to the current one, revealing the nearest smaller element to the right. The distance from the current index to this smaller element defines how many subarrays can extend to the right with the current element as minimum. This symmetric approach complements the left pass and completes the boundary calculation.

Interview Quick-Check

Core Logic

Iterate from right to left using a monotonic increasing stack with '>=' comparison to find nearest smaller elements on the right, computing right distances.

State & Boundaries

If no smaller element exists to the right, the distance is the length of the array minus the current index, representing subarrays extending to the end.

Common Pitfalls & Bugs

Using '>=' instead of '>' ensures correct counting of subarrays when duplicates exist, avoiding double counting.

Accumulate Total Sum of Subarray Minimums Using Precomputed Distances

34ans = 0
36for i in range(n):
37    ans += arr[i] * left[i] * right[i]
38    ans %= mod
40return ans

Objective

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.

Key Insight

Each element's contribution is its value times the number of subarrays it is minimum for, which equals left[i] * right[i]. Summing these contributions for all elements yields the final answer. Taking modulo at each addition prevents integer overflow and conforms to problem constraints.

Interview Quick-Check

Core Logic

Multiply each element by its left and right distances to count subarrays where it is minimum, then sum all contributions modulo 10^9 + 7.

State & Boundaries

Modulo operation is applied after each addition to keep the result within integer limits.

Common Pitfalls & Bugs

Forgetting to apply modulo at each step can cause integer overflow and incorrect results.

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.

Line 15 Core

left[i] = i - stack[-1]

Calculate distance to previous less element.

Distance is the difference between current index and index of nearest smaller element, representing how far left the current element can extend as minimum.

Line 28 Core

right[i] = stack[-1] - i

Calculate distance to next less element.

Distance is the difference between index of nearest smaller element and current index, representing how far right the current element can extend as minimum.

Line 8 Core

stack = []

Initialize an empty stack to track indices for left pass.

The stack maintains indices of elements in ascending order to efficiently find previous less elements.

Line 12 Core

stack.pop()

Remove the top element from the stack.

Popping the stack updates the candidate for the previous less element, enabling correct distance calculation.

Line 16 Core

else:

Handle case where no previous less element exists.

If stack is empty, the current element is the smallest so far, so distance is current index plus one, covering all elements to the left.

Line 17 Core

left[i] = i + 1

Set distance to previous less element as current index plus one.

This correctly counts subarrays starting from the beginning of the array where the current element is minimum.

Line 19 Core

stack.append(i)

Push current index onto the stack.

Adding current index maintains the monotonic stack invariant for future iterations.

Line 25 Core

stack.pop()

Remove the top element from the stack.

Popping updates the candidate for the next less element, enabling correct distance calculation.

Line 29 Core

else:

Handle case where no next less element exists.

If stack is empty, the current element is the smallest to the right, so distance is from current index to end of array.

Line 30 Core

right[i] = n - i

Set distance to next less element as array length minus current index.

This counts subarrays extending to the end of the array where the current element is minimum.

Line 32 Core

stack.append(i)

Push current index onto the stack.

Maintains the monotonic stack invariant for the right pass.

Line 38 Core

ans %= mod

Apply modulo to keep the answer within integer limits.

Modulo operation prevents integer overflow and ensures the result matches problem constraints.

Line 6 Standard

left = [0] * n

Initialize the left distances array with zeros.

This array will store the count of contiguous elements to the left where the current element is minimum.

Line 7 Standard

right = [0] * n

Initialize the right distances array with zeros.

This array will store the count of contiguous elements to the right where the current element is minimum.

Line 14 Standard

if stack:

Check if the stack is not empty after popping.

If the stack is not empty, the top element is the nearest smaller element to the left.

Line 27 Standard

if stack:

Check if the stack is not empty after popping.

If the stack is not empty, the top element is the nearest smaller element to the right.

Line 36 Standard

for i in range(n):

Iterate over all elements to accumulate their contributions.

This loop sums the weighted contributions of each element based on precomputed distances.

Line 40 Standard

return ans

Return the final computed answer.

Returns the sum of subarray minimums modulo 10^9 + 7 as required by the problem.

Line 3 Standard

mod = 10**9 + 7

Define the modulo constant for the final answer.

Using modulo 10^9 + 7 ensures the result fits within integer limits and matches problem requirements for large sums.

Line 10 Standard

for i in range(n):

Iterate over the array from left to right.

This loop computes the distance to the previous less element for each index.

Line 21 Standard

stack = []

Reset the stack to empty for the right pass.

Clearing the stack prepares it for the next less element computation from the right side.

Line 23 Standard

for i in range(n - 1, -1, -1):

Iterate over the array from right to left.

This loop computes the distance to the next less element for each index.

Line 34 Standard

ans = 0

Initialize the accumulator for the answer.

This variable will hold the sum of all subarray minimum contributions modulo 10^9 + 7.

Line 4 Basic

n = len(arr)

Store the length of the input array.

Caching the length avoids repeated calls to len(arr) and improves readability.

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?

Because the distances represent how far the element can extend to the left and right without encountering a smaller element, the product counts all subarrays including this element as the minimum exactly once.

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

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)`

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Compute Distances to Previous Less Elements Using Monotonic Stack

Compute Distances to Next Less Elements Using Monotonic Stack

Accumulate Total Sum of Subarray Minimums Using Precomputed Distances

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.