Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Monotonic Stack: Subarray Minimums and Histograms

Editorial

Every subarray's minimum, added up

Sum of Subarray Minimums asks for the minimum of every contiguous subarray, all added up. For [3, 1, 2, 4] the ten subarrays have minimums 3, 1, 1, 1, 1, 1, 1, 2, 2 and 4, which sum to 17.

The direct way tries every start and walks every end, keeping a running minimum:

def sum_subarray_mins(arr):
    total = 0
    for i in range(len(arr)):            # every start
        low = arr[i]
        for j in range(i, len(arr)):     # every end, keeping the running minimum
            low = min(low, arr[j])
            total += low
    return total % (10**9 + 7)

That's n(n + 1)/2 subarrays, so O(n²). On our judge, with random values:

ValuesEvery start and endOne pass with a stack
1,250196 ms0.7 ms
2,500762 ms1.3 ms
5,0003,075 ms2.6 ms

Doubling the length made the brute force about four times slower.

Turn the question around. Every subarray's minimum is one of the values, so ask, for each value: how many subarrays is it the minimum of? Exactly those that contain it and nothing smaller. They start anywhere after its previous smaller value and end anywhere before its next smaller value. With left choices of start and right choices of end, the value is the minimum of left × right subarrays, and its share of the sum is value × left × right.

Bars for 1, 4, 3, 5, 6, 2. The bar 3 at index 2 is highlighted; the 1 at index 0 and the 2 at index 5 are walls, the nearest smaller values. Between them, starts at 1 or 2 and ends at 2, 3 or 4, and the dashed rectangle of height 3 between the walls has area 12. A focal line reads: 2 × 3 = 6 subarrays have 3 as their minimum.

Equal values: stop on one side only

Ties need care. In [2, 2], the subarray [2, 2] has two equal minimums, and it must be counted once. If both values stop at an equal neighbour, neither claims it; if both walk past equal neighbours, both claim it. We counted all three rules:

RuleTotal for [2, 2]
stop at an equal value on the right, not on the left6, correct
stop at an equal value on both sides4 ([2, 2] missed)
walk past equal values on both sides8 ([2, 2] counted twice)

So the left wall is the previous strictly smaller value, and the right wall is the next smaller or equal value. Then each subarray goes to exactly one of its equal minimums, the rightmost.

Two bars of height 2 and the three subarrays [2], [2] and [2, 2]. Three rows show who claims [2, 2]: stopping at equals on both sides, nobody, giving 4; walking past equals on both sides, both bars, giving 8; stopping at an equal on the right only, bar 1 alone, giving 6. A focal line reads: stop at an equal value on one side only.

One pass finds both walls

The stack from Monotonic Stack: Next Greater and Smaller Elements gives both walls at once. Keep indices whose values rise from bottom to top, and pop while the top is at least x. The value popped has just met its right wall, x, the next smaller or equal value. Its left wall is the new top, strictly smaller, since every equal value was popped. So a pop can write value × left × right straight away. A 0 after the last value pops whatever is left:

Sum of subarray minimums of [3, 1, 2, 4] — Each pop writes that value's share: value × starts × ends.

Sum of Subarray Minimums wants the total modulo 10⁹ + 7, because it grows fast. C++ and Java keep 64-bit products; JavaScript keeps each product under 2⁵³:

int sumSubarrayMins(const vector<int>& arr) {
    const long long MOD = 1'000'000'007;
    int n = arr.size();
    long long total = 0;
    vector<int> stack;                       // indices; their values rise from bottom to top
    for (int i = 0; i <= n; i++) {
        int x = i < n ? arr[i] : 0;          // a 0 after the end pops everything left
        while (!stack.empty() && arr[stack.back()] >= x) {
            int j = stack.back();
            stack.pop_back();
            long long left = j - (stack.empty() ? -1 : stack.back());   // starts: back to the previous smaller
            long long right = i - j;                                    // ends: up to this smaller-or-equal x
            total = (total + arr[j] * left % MOD * right) % MOD;
        }
        stack.push_back(i);
    }
    return (int)total;
}

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n, total = len(arr), 0
    stack = []                           # indices; their values rise from bottom to top
    for i in range(n + 1):
        x = arr[i] if i < n else 0       # a 0 after the end pops everything left
        while stack and arr[stack[-1]] >= x:
            j = stack.pop()
            left = j - (stack[-1] if stack else -1)   # starts: back to the previous smaller
            right = i - j                # ends: up to this smaller-or-equal x
            total += arr[j] * left * right
        stack.append(i)
    return total % MOD

static int sumSubarrayMins(int[] arr) {
    final long MOD = 1_000_000_007L;
    int n = arr.length;
    long total = 0;
    Deque<Integer> stack = new ArrayDeque<>();        // indices; their values rise from bottom to top
    for (int i = 0; i <= n; i++) {
        int x = i < n ? arr[i] : 0;                    // a 0 after the end pops everything left
        while (!stack.isEmpty() && arr[stack.peek()] >= x) {
            int j = stack.pop();
            long left = j - (stack.isEmpty() ? -1 : stack.peek());   // starts: back to the previous smaller
            long right = i - j;                                       // ends: up to this smaller-or-equal x
            total = (total + arr[j] * left % MOD * right) % MOD;
        }
        stack.push(i);
    }
    return (int) total;
}

function sumSubarrayMins(arr) {
    const MOD = 1_000_000_007;
    const n = arr.length;
    let total = 0;
    const stack = [];                        // indices; their values rise from bottom to top
    for (let i = 0; i <= n; i++) {
        const x = i < n ? arr[i] : 0;        // a 0 after the end pops everything left
        while (stack.length && arr[stack[stack.length - 1]] >= x) {
            const j = stack.pop();
            const left = j - (stack.length ? stack[stack.length - 1] : -1);   // starts: back to the previous smaller
            const right = i - j;             // ends: up to this smaller-or-equal x
            total = (total + arr[j] * left * right) % MOD;   // each product stays under 2^53
        }
        stack.push(i);
    }
    return total;
}

Each printed 17 444 6 for [3, 1, 2, 4], [11, 81, 94, 43, 3], [2, 2]: LeetCode's two examples and the tie case. Every index is pushed and popped once: O(n) time, O(n) space.

The same walls make the largest rectangle

Largest Rectangle in Histogram asks for the biggest rectangle that fits under a row of bars. The best rectangle of a bar's own height reaches left and right until a shorter bar stops it, which are the same two walls. So one pass measures every bar: when a bar is popped by a shorter one, its rectangle spans from just after the new top to just before the bar that popped it:

Largest rectangle in [2, 1, 5, 6, 2, 3] — Each pop measures one bar's widest rectangle; the best one is kept.

int largestRectangleArea(const vector<int>& h) {
    int n = h.size(), best = 0;
    vector<int> stack;                       // indices of bars still growing to the right
    for (int i = 0; i <= n; i++) {
        int x = i < n ? h[i] : 0;            // a height-0 bar at the end measures everything left
        while (!stack.empty() && h[stack.back()] >= x) {
            int height = h[stack.back()];
            stack.pop_back();
            int left = stack.empty() ? -1 : stack.back();   // the nearest shorter bar on the left
            best = max(best, height * (i - left - 1));      // it spans everything between the two shorter bars
        }
        stack.push_back(i);
    }
    return best;
}

def largest_rectangle_area(h):
    n, best = len(h), 0
    stack = []                           # indices of bars still growing to the right
    for i in range(n + 1):
        x = h[i] if i < n else 0         # a height-0 bar at the end measures everything left
        while stack and h[stack[-1]] >= x:
            height = h[stack.pop()]
            left = stack[-1] if stack else -1      # the nearest shorter bar on the left
            best = max(best, height * (i - left - 1))   # it spans everything between the two shorter bars
        stack.append(i)
    return best

static int largestRectangleArea(int[] h) {
    int n = h.length, best = 0;
    Deque<Integer> stack = new ArrayDeque<>();        // indices of bars still growing to the right
    for (int i = 0; i <= n; i++) {
        int x = i < n ? h[i] : 0;                      // a height-0 bar at the end measures everything left
        while (!stack.isEmpty() && h[stack.peek()] >= x) {
            int height = h[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();   // the nearest shorter bar on the left
            best = Math.max(best, height * (i - left - 1));   // it spans everything between the two shorter bars
        }
        stack.push(i);
    }
    return best;
}

function largestRectangleArea(h) {
    const n = h.length;
    let best = 0;
    const stack = [];                        // indices of bars still growing to the right
    for (let i = 0; i <= n; i++) {
        const x = i < n ? h[i] : 0;          // a height-0 bar at the end measures everything left
        while (stack.length && h[stack[stack.length - 1]] >= x) {
            const height = h[stack.pop()];
            const left = stack.length ? stack[stack.length - 1] : -1;   // the nearest shorter bar on the left
            best = Math.max(best, height * (i - left - 1));             // it spans everything between the two shorter bars
        }
        stack.push(i);
    }
    return best;
}

Each printed 10 4 9 for [2, 1, 5, 6, 2, 3], [2, 4], [1, 2, 3, 4, 5]. In the rising one, no bar is ever stopped until the 0 at the end: without it, nothing would be measured.

Now you stretch the bars

Below, pick a bar and stretch its rectangle left and right, one bar at a time. A shorter bar stops it, and stretching past one is refused. When both sides are stopped, the area and the number of subarrays the bar is the minimum of appear. Then let the stack find every wall in one pass and compare.

Stretch the Bar: each bar's rectangle, until a shorter bar stops it

Rows, valleys and ranges

Maximal Rectangle asks for the largest rectangle of 1s in a grid. Go row by row: for each column, count the 1s stacked up to this row. Each row is then a histogram, and the answer is the best largest rectangle over the rows:

LeetCode's 4 by 5 grid of 0s and 1s. Under the third row, its heights 3, 1, 3, 2, 2 are drawn as bars, the 1s above each cell stacked up, and the rectangle of height 2 and width 3 across the last three bars is highlighted with area 6. A focal line reads: the largest rectangle of 1s is 6, from row 2's histogram.
def maximal_rectangle(matrix):
    if not matrix:
        return 0
    heights = [0] * len(matrix[0])
    best = 0
    for row in matrix:                   # each row turns the 1s above it into a histogram
        for c, cell in enumerate(row):
            heights[c] = heights[c] + 1 if cell == "1" else 0
        best = max(best, largest_rectangle_area(heights))
    return best

It returned 6, 0 and 1 for LeetCode's three grids, using largest_rectangle_area from above. O(rows × columns).

Trapping Rain Water asks how much rain the bars hold. On the stack, keep walls whose heights fall. A taller bar closes a valley: pop its floor, and the water above the floor reaches the lower of the two walls, across the gap between them. One pop, one layer:

Rain on [4, 2, 0, 3, 2, 5] — Each pop of a valley floor adds one layer of water.

def trap(height):
    water, stack = 0, []                 # indices of the walls so far; their heights fall from bottom to top
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = height[stack.pop()]  # the floor of a valley
            if not stack:
                break                    # no wall on the left: water would run off
            left = stack[-1]
            depth = min(height[left], h) - bottom
            water += depth * (i - left - 1)   # one layer, as wide as the gap between the walls
        stack.append(i)
    return water

It returned 6 and 9 for LeetCode's two examples. Two Pointers solves the same problem from both ends with O(1) space.

Sum of Subarray Ranges adds up max − min over every subarray: the sum of all the maximums minus the sum of all the minimums, each by the same contribution pass with the comparison flipped:

def sum_subarray_ranges(nums):
    def total(better):                   # the sum of every subarray's best value, by contributions
        n, s, stack = len(nums), 0, []
        for i in range(n + 1):
            while stack and (i == n or not better(nums[stack[-1]], nums[i])):
                j = stack.pop()
                left = j - (stack[-1] if stack else -1)
                s += nums[j] * left * (i - j)
            stack.append(i)
        return s
    biggest = total(lambda top, x: top > x)    # a top bigger than x survives: sums of maxima
    smallest = total(lambda top, x: top < x)   # a top smaller than x survives: sums of minima
    return biggest - smallest

It returned 4, 4 and 59 for LeetCode's three examples.

Spotting it, and when it breaks

The clues. A sum, count or best value over all subarrays involving their minimum or maximum; "the largest rectangle"; bars, heights, histograms, skylines; water between walls. Anything where each element owns the stretch between its nearest smaller (or bigger) neighbours.

The near-misses. The minimum of each window of a fixed size k is a monotonic deque (Sliding Window Maximum, in Queues & Deques). A single best subarray sum is Kadane's Algorithm. Water held between just two walls you choose is Container With Most Water, a two-pointer problem.

When it breaks. Overflow: the sums grow as n³ in the worst case. When the question isn't about the nearest smaller value on each side (say, the second smallest of every subarray), the two walls don't describe the answer any more.

Bugs that cost a submission

Strict on both sides, or on neither. The table above: [2, 2] came out 8 or 4 instead of 6.

Forgetting the modulo.

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n, total = len(arr), 0
    stack = []                           # indices; their values rise from bottom to top
    for i in range(n + 1):
        x = arr[i] if i < n else 0       # a 0 after the end pops everything left
        while stack and arr[stack[-1]] >= x:
            j = stack.pop()
            left = j - (stack[-1] if stack else -1)   # starts: back to the previous smaller
            right = i - j                # ends: up to this smaller-or-equal x
            total += arr[j] * left * right
        stack.append(i)
    return total                         # no modulo

On 30,000 random values up to 30,000 it returned 8,260,700,457, past the 2,147,483,647 a 32-bit int can hold; the answer LeetCode wants is 260,700,401. In C++ or Java without 64-bit products the total would already be wrong long before the end.

No sentinel at the end.

def largest_rectangle_area(h):
    best, stack = 0, []
    for i in range(len(h)):              # no 0 at the end
        while stack and h[stack[-1]] >= h[i]:
            height = h[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best                          # bars still on the stack were never measured

It returned 0 for [2, 4] and 0 for [1, 2, 3, 4, 5]: those bars are never stopped, so they're never measured. The answers are 4 and 9.

Check yourself

Quiz

1 / 6

Multiple choice

In [1, 4, 3, 5, 6, 2], how many subarrays is the 3 the minimum of?

Practice problems

From easier to harder:

  1. Sum of Subarray Minimums: value × left × right, one side strict.
  2. Sum of Subarray Ranges: maximums minus minimums.
  3. Largest Rectangle in Histogram: the same walls, as widths.
  4. Trapping Rain Water: one layer per pop.
  5. Maximal Rectangle: a histogram per row.

That's the last lesson on stacks. Next, Queues & Deques: first in, first out, and both ends at once.