Generated by Codex with GPT-5

Quick facts

  • Difficulty: MEDIUM
  • Problem: Sum of Subarray Minimums
  • Main tags: Array, Dynamic Programming, Stack, Monotonic Stack
  • Frequency in source list: 22.1

What the problem is really asking

For every contiguous subarray, take its minimum value. Then add all of those minimums together.

That sounds simple until the number of subarrays is considered. An array of length n has about n^2 / 2 subarrays, so listing each one and recomputing its minimum quickly becomes too slow.

The real interview question is this:

“Can each element tell us how many subarrays use it as the minimum, so we never have to enumerate all subarrays directly?”

That shift in viewpoint is the whole problem.

Why brute force is not enough

The obvious solution is:

  1. Pick every start index.
  2. Extend the subarray to every possible end index.
  3. Track the running minimum.
  4. Add it to the answer.

That improves on the worst possible brute force because the minimum can be updated incrementally, but it is still O(n^2).

For small inputs that is fine. For the real constraints, it is not.

So the optimal solution needs to answer a different question:

“For index i, in how many subarrays is arr[i] the minimum?”

If that count is known, then arr[i] contributes:

arr[i] * number_of_subarrays_where_it_is_the_minimum

Summing those contributions over all indices gives the final answer.

The key insight: count each value’s contribution

Focus on one element, arr[i].

To make arr[i] the minimum of a subarray:

  • the subarray must start after the nearest smaller value on the left
  • the subarray must end before the next smaller-or-equal value on the right

Those two boundaries tell exactly how many choices exist for the left edge and the right edge.

If:

  • left_boundary is the index of the previous element that is strictly smaller
  • right_boundary is the index of the next element that is smaller or equal

then:

  • there are i - left_boundary valid choices for the start
  • there are right_boundary - i valid choices for the end

So the number of subarrays where arr[i] is the chosen minimum is:

(i - left_boundary) * (right_boundary - i)

And the contribution of arr[i] is:

arr[i] * (i - left_boundary) * (right_boundary - i)

Why the tie-breaking matters for duplicates

The subtle part is duplicate values.

If two equal values are both allowed to claim the same subarray, that subarray gets counted twice. If neither claims it, it gets missed.

So the implementation has to break ties consistently. A clean convention is:

  • on the left, look for the previous value that is strictly smaller
  • on the right, look for the next value that is smaller or equal

That means equal values are assigned to exactly one side of the tie, which makes every subarray count exactly once.

This is one of the most important details to explain in an interview, because it shows the monotonic-stack logic is understood rather than memorized.

A concrete example

Take arr = [3, 1, 2, 4].

For 1 at index 1:

  • there is no smaller value on the left, so the start can be index 0 or 1
  • there is no smaller-or-equal value on the right, so the end can be index 1, 2, or 3

That gives 2 * 3 = 6 subarrays where 1 is the minimum, so this single element contributes 1 * 6 = 6.

Doing the same for every index gives:

  • 3 contributes 3
  • 1 contributes 6
  • 2 contributes 4
  • 4 contributes 4

Total: 17

That matches the expected answer.

How to derive the optimal solution in an interview

A strong explanation usually goes in this order:

  1. Say that direct enumeration is too slow because there are too many subarrays.
  2. Reframe the problem around each element’s contribution.
  3. Observe that each element needs the nearest boundary on the left where something smaller appears.
  4. Observe that it also needs the nearest boundary on the right where something smaller or equal appears.
  5. Use a monotonic increasing stack to compute both boundaries in linear time.
  6. Multiply the number of left choices by the number of right choices to get each element’s total contribution.

This is the kind of derivation interviewers want. The stack is not the answer by itself. The contribution formula is the real answer, and the stack is the tool that makes it efficient.

Python solution

The implementation below uses two helper passes:

  • one pass finds the previous strictly smaller index for every position
  • one pass finds the next smaller-or-equal index for every position

That produces a clean and easy-to-defend O(n) solution.

from typing import List


MOD = 10**9 + 7


def previous_strictly_smaller_indices(values: List[int]) -> List[int]:
    """
    For each index, return the nearest index to the left whose value is
    strictly smaller. If none exists, return -1.

    The stack stores indices in increasing-value order.
    """
    previous_indices = [-1] * len(values)
    increasing_stack: List[int] = []

    for index, value in enumerate(values):
        while increasing_stack and values[increasing_stack[-1]] >= value:
            increasing_stack.pop()

        if increasing_stack:
            previous_indices[index] = increasing_stack[-1]

        increasing_stack.append(index)

    return previous_indices


def next_smaller_or_equal_indices(values: List[int]) -> List[int]:
    """
    For each index, return the nearest index to the right whose value is
    smaller than or equal to the current value. If none exists, return len(values).

    This tie-breaking pairs with previous_strictly_smaller_indices so duplicate
    values are counted exactly once.
    """
    next_indices = [len(values)] * len(values)
    increasing_stack: List[int] = []

    for index in range(len(values) - 1, -1, -1):
        value = values[index]

        while increasing_stack and values[increasing_stack[-1]] > value:
            increasing_stack.pop()

        if increasing_stack:
            next_indices[index] = increasing_stack[-1]

        increasing_stack.append(index)

    return next_indices


def sum_subarray_minimums(values: List[int]) -> int:
    if not values:
        return 0

    previous_smaller = previous_strictly_smaller_indices(values)
    next_smaller_or_equal = next_smaller_or_equal_indices(values)

    total = 0

    for index, value in enumerate(values):
        left_choices = index - previous_smaller[index]
        right_choices = next_smaller_or_equal[index] - index

        # Every combination of a valid left edge and right edge creates a
        # subarray in which values[index] is the chosen minimum.
        contribution = value * left_choices * right_choices
        total = (total + contribution) % MOD

    return total


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        return sum_subarray_minimums(arr)

Why this works

Every subarray has exactly one minimum value that must be credited to one index.

For a fixed index i, the previous strictly smaller element marks the first place on the left where arr[i] would stop being the minimum. Likewise, the next smaller-or-equal element marks the first place on the right where arr[i] would stop being the chosen minimum under the tie-breaking rule.

That creates a rectangular count of valid choices:

  • choose any start position from left_boundary + 1 through i
  • choose any end position from i through right_boundary - 1

Those choices are independent, so the total number of qualifying subarrays is the product of the two counts.

The monotonic stack makes boundary discovery linear because each index is pushed once and popped at most once. That is why the full algorithm is O(n) time and O(n) space.

Interview follow-ups

Can this be solved in one pass instead of building two boundary arrays?

Yes. Another optimal approach uses a monotonic stack while scanning left to right and computes, for each position, the sum of minimums of all subarrays ending at that position. That version is also O(n), and some people prefer it because it avoids storing two separate boundary arrays. The tradeoff is readability. The contribution-counting version in this note is usually easier to derive on a whiteboard, easier to explain, and easier to debug under pressure.

What changes if the problem asks for subarray maximums instead?

The pattern is the same, but the inequalities flip. Instead of searching for smaller boundaries, the solution searches for larger boundaries so each element can count how many subarrays treat it as the maximum. The same duplicate-handling issue still exists, so a consistent tie-breaking rule is still necessary. Once that rule is chosen, the exact same contribution formula applies.

Why not use previous smaller on both sides, or smaller-or-equal on both sides?

Because duplicates would be handled incorrectly. If both sides use strict comparison, equal values can leave gaps where no index claims a subarray. If both sides use non-strict comparison, multiple equal values can claim the same subarray. The asymmetry is deliberate: one side must be strict and the other non-strict so every subarray is counted once and only once.

What if the interviewer starts with the O(n^2) solution and asks for incremental improvement?

That is a normal interview path. A solid progression is to begin with the nested-loop approach that keeps a running minimum, then explain that it is still quadratic because every subarray is visited. From there, shift to the contribution view and show that the real bottleneck is finding the nearest blocking boundary on each side. That naturally motivates the monotonic stack. The key is to present the optimal method as a consequence of the quadratic bottleneck, not as a disconnected trick.

Why is the answer taken modulo 10^9 + 7?

Because the raw sum can grow very large. Even though Python integers can handle that growth, the problem requires returning the value modulo 10^9 + 7, so the implementation applies the modulus as contributions are added. In languages with fixed-width integers, taking the modulus during accumulation is also important for preventing overflow.

Practical takeaway

This problem is a classic example of the “contribution counting + monotonic stack” pattern.

The reusable template is:

  • do not enumerate every subarray
  • let each element count how many subarrays choose it
  • find the nearest blocking boundary on both sides
  • multiply left choices by right choices
  • use consistent tie-breaking for duplicates

Once that pattern is recognized, a problem that looks quadratic becomes a clean linear-time solution.