Coding Interview Patterns Module 8 – Stacks and monotonic stacks
Contribution counting with monotonic stacks
Sum the minimum of every subarray in O(n): count how many subarrays each element is the minimum of, with monotonic stacks, ties counted once.
What you will learn
- Count how many subarrays have each element as their minimum, from its nearest smaller elements
- Compute the sum of the minimums of all subarrays in O(n) with one pass of a monotonic stack
- Prove that every subarray is counted exactly once when values repeat
- Prevent overflow and lost precision under a modulus of 10⁹ + 7 in Java, C++, Go and JavaScript
- Compute the sums of the maximums and of the spreads (maximum minus minimum) the same way
Before you start
What you’ll learn · Before you start
What you will learn
- Count how many subarrays have each element as their minimum, from its nearest smaller elements
- Compute the sum of the minimums of all subarrays in O(n) with one pass of a monotonic stack
- Prove that every subarray is counted exactly once when values repeat
- Prevent overflow and lost precision under a modulus of 10⁹ + 7 in Java, C++, Go and JavaScript
- Compute the sums of the maximums and of the spreads (maximum minus minimum) the same way
Before you start
On this page
contribution counting: Summing a value over all subarrays by asking, for each element, in how many subarrays it decides the value, and adding its value times that count, instead of visiting every subarray. turns a sum over all subarrays into a sum over the elements: in 4, 2, 5, 3 the 2 is the minimum of 6 subarrays, so it adds 2 × 6 = 12. Instead of finding the minimum of each of the n(n + 1)/2 subarrays, it asks how many subarrays each element is the minimum of, and adds value × count. That count is a product of two choices, where such a subarray may start and where it may end, bounded by the nearest smaller element on each side, which a monotonic stack: A stack whose values stay in order from bottom to top, because each new item first pops every item it settles. It finds the nearest earlier or later larger, or smaller, item for every item in one pass. More in “Stack patterns: nesting and undo” finds for every element in O(n). The whole sum then takes O(n) time instead of O(n²). Its best-known case is the sum of subarray minimums, stated here as the cheapest item of every basket on a shelf. Sums of maximums and of spreads, maximum minus minimum, follow from the same count.
The problem: the cheapest item of every basket
The problem
A shelf holds n items in a row, with prices p[0..n − 1]. A basket is any run of one or more neighbouring items,
and its floor is the price of its cheapest item. Return the sum of the floors of all n(n + 1)/2 baskets, modulo
10⁹ + 7. Limits: 1 ≤ n ≤ 300,000 and 1 ≤ p[i] ≤ 10⁹.
Four examples, which every program in this lesson runs:
[4, 2, 5, 3]gives 27: the four single items add 14, the three pairs 2 + 2 + 3, the two triples 2 + 2 and the whole shelf 2.[2, 2, 2]gives 12: six baskets, each with a floor of 2.[7]gives 7.[10⁹, 10⁹]gives 999,999,986, which is 3 × 10⁹ reduced modulo 10⁹ + 7.
The brute force: every basket with its cheapest item
Start a basket at every item and extend it to the right, keeping the cheapest price seen so far and adding it to the total. The run counts the baskets on random shelves:
"""The sum of the cheapest price of every basket, the brute force: every run of neighbouring items."""
import random
MOD = 1_000_000_007
def floor_total_brute(prices):
"""The sum, modulo 10**9 + 7, of the lowest price of every basket, and how many baskets were tried."""
total = baskets = 0
for i in range(len(prices)):
lowest = prices[i]
for j in range(i, len(prices)): # the basket of items i..j
lowest = min(lowest, prices[j])
total = (total + lowest) % MOD
baskets += 1
return total, baskets
print(floor_total_brute([4, 2, 5, 3])[0])
print(floor_total_brute([2, 2, 2])[0])
print(floor_total_brute([7])[0])
print(floor_total_brute([10**9, 10**9])[0])
rng = random.Random(907)
for n in (1_000, 2_000):
shelf = [rng.randint(1, 10**9) for _ in range(n)]
print(f"{n:,} items: {floor_total_brute(shelf)[1]:,} baskets")Output
27 12 7 999999986 1,000 items: 500,500 baskets 2,000 items: 2,001,000 baskets
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 floors_brute.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
There is no shortcut inside the loops: every one of the n(n + 1)/2 baskets is visited, 45,000,150,000 of them at the limit of 300,000 items. At 10⁸ simple steps a second that is seven and a half minutes of C++. The total itself grows just as fast: it can reach 4.5 × 10¹⁹, beyond the largest 64-bit integer, about 9.2 × 10¹⁸, which is why the problem asks for it modulo 10⁹ + 7.
Checkpoint
Check: What visiting every basket costs
What to notice
Turn the question round: for each item, in how many baskets is it the cheapest? Such a basket must start after the nearest cheaper item on the left and end before the nearest cheaper item on the right, and any such start and end will do. In the table below, item 1 is the cheapest of 2 starts × 3 ends = 6 baskets, so it adds 2 × 6 = 12.
The baskets an item is the cheapest of form one block of starts and ends
Text description of the diagram
The table has a row for each item where a basket can start (0 to 3) and a column for each item where it can end (0 to 3), so each of the ten baskets of the shelf 4, 2, 5, 3 is one cell on or above the diagonal. Each cell shows the basket's cheapest price.
- Row 0 reads 4, 2, 2, 2: the basket of item 0 alone costs 4 at its cheapest, and every longer basket starting there contains item 1, price 2.
- Row 1 reads 2, 2, 2: every basket starting at item 1 contains it.
- Row 2 reads 5, 3, and row 3 reads 3.
Thick outlines group the cells by the item that is their cheapest. Item 0 owns one cell, item 2 one cell, item 3 the two cells of column 3 in rows 2 and 3, and item 1, shaded, a block of 2 rows by 3 columns: baskets that start at item 0 or 1 and end at item 1, 2 or 3. That block has 2 × 3 = 6 cells, so item 1 adds 2 × 6 = 12 to the total. The four blocks add 4 + 12 + 5 + 6 = 27, the sum of all ten cells.
The nearest cheaper item on each side is the question that a monotonic stack answers, as in the lesson on next greater elements. Equal prices need one more rule, so that a basket with two cheapest items is counted once.
Checkpoint
Check: The baskets each item is the cheapest of
Practice that adapts to you
Practise this lesson
6 questions about 8 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Each item’s share, in one pass with a stack Pro: opens with a Pro, Premium or Ultimate pass
- A dry run on [4, 2, 5, 3]
- Equal prices: strict on one side, and the proof that each basket counts once
- The modulus, and the products that overflow on the way
- The code in 14 languages, each exact under the modulus
- A stress test, and edge cases
- Maximums and spreads: the same loop, reversed
- Practise: the total spread of every basket
- Add up the price spread of every basket
- Variants and follow-up questions, answered
- Interview questions
- Your sum of subarray minimums comes out too large whenever the input repeats values. Explain why, fix it, and prove that every subarray is now counted exactly once.
- The sum of subarray minimums for 300,000 prices of up to 10⁹ must be returned modulo 10⁹ + 7. Where can a Java or JavaScript solution lose exactness, and how do you keep every step exact?
- For an array of daily prices, return the sum over all subarrays of (maximum − minimum), modulo 10⁹ + 7. Give an O(n) method, the cost of the naive one at n = 10⁵, and how you handle the subtraction under the modulus.
- Key takeaways
1 diagram · 5 runnable examples (Java, JavaScript, Python) · 1 exercise with sample tests · 3 interview answers · about 36 minutes
Opening this part with your pass…
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- contribution counting
- Summing a value over all subarrays by asking, for each element, in how many subarrays it decides the value, and adding its value times that count, instead of visiting every subarray.
References
- Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values (Journal of Algorithms 14(3)) (Journal of Algorithms (Berkman, Schieber and Vishkin))
- Built-in types: numeric types (int has unlimited precision) (Python Software Foundation)
- Number.MAX_SAFE_INTEGER (MDN Web Docs (Mozilla))
- BigInt (MDN Web Docs (Mozilla))
- The Java Language Specification, Java SE 25: multiplication operator (15.17.1) (Oracle)
- The Java Language Specification, Java SE 25: remainder operator (15.17.3) (Oracle)
- Arithmetic operators (integer overflow and the sign of %) (cppreference.com)
- The Go Programming Language Specification: Arithmetic operators (The Go Authors)
- Arithmetic operators (C# reference): integer arithmetic overflow (Microsoft)
- PHP manual: integers (size and overflow) (The PHP Group)
- The Swift Programming Language: advanced operators (overflow operators) (Swift.org)
- Numbers in Dart (Dart (Google))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress