Workspace

Problem workspace

3 day streakD

Sum of Subarray Minimums

MediumStacksAreas & contributions

The challenge

Sum the minimum of every nonempty contiguous subarray, modulo 1,000,000,007.

Positive integer values up to 30,000; length ≤ 30,000. Empty input returns 0.

Example

[3,1,2,4] → 17.

Use the walkthrough below to inspect the input and each state change.

See Sum of Subarray Minimums, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.30112243Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 10

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: [3,1,2,4]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Use previous strictly smaller and next smaller-or-equal boundaries.

Indices are zero-based. C++ uses C++17 or later.

def solve(values):
    mod = 1_000_000_007
    stack, total = [], 0
    n = len(values)
    for right in range(n + 1):
        # Previous strictly smaller, next smaller-or-equal.
        while stack and (right == n or values[stack[-1]] >= values[right]):
            i = stack.pop()
            left = stack[-1] if stack else -1
            total = (total + values[i] * (i - left) * (right - i)) % mod
        if right < n: stack.append(right)
    return total

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap