Histogram Expansion

When To Use

Use this when choosing an index as the minimum height/value and expanding as far as possible improves the objective.

Template

for each i:
    left = previous smaller boundary
    right = next smaller boundary
    use full range (left + 1, right - 1)

This is a boundary problem, but the answer usually uses the widest range rather than summing every range.

Problems

Largest Rectangle in Histogram

Problem: find the largest rectangle under histogram bars.

Pattern: each bar is the limiting height for its widest range.

Applied pseudocode:

left[i] = previous index with height < heights[i]
right[i] = next index with height < heights[i]
 
for i = 0; i < n; i++:
    width = right[i] - left[i] - 1
    ans = max(ans, heights[i] * width)

Maximal Rectangle

Problem: largest all-1 rectangle in a binary matrix.

Pattern: turn each row into histogram heights and reuse histogram rectangle.

Maximum Subarray Min Product

Problem: maximize min(subarray) * sum(subarray).

Pattern: each value is the minimum over its widest range; use prefix sums.

Valid Subarray Size

Problem: find a subarray where min(subarray) * len > threshold.

Pattern: each value is the minimum over its widest range.

Count All-1 Submatrices

Problem: count all submatrices filled with 1.

Pattern: histogram heights plus previous-smaller compression.