Largest Rectangle in a Histogram and Maximal Rectangle

The histogram and maximal-rectangle problems are an extension topic beyond most interviews, but they are well-known hard questions at large companies; the technique also solves any "pick a subarray scored by its minimum" problem in linear time.

Intuition

Largest rectangle in a histogram. In the best rectangle, some bar is the lowest one, and the rectangle is as wide as possible around it. So for every bar i, find how far it can stretch:

• left[i]: the leftmost index such that every bar from there to i is at least heights[i];
• right[i]: the rightmost such index.

The candidate area is heights[i] * (right[i] - left[i] + 1), and the answer is the maximum over all i. A naive scan is O(n^2); two techniques make it O(n).

Hanging lines with jumps. Think of a vertical line hanging from the top of bar i that slides left while the bars stay at least as tall. When the next bar to the left, j = left[i] - 1, is at least as tall as bar i, bar i can also reach everything bar j can reach (those bars are at least heights[j] >= heights[i]), so jump straight to left[j] instead of stepping one bar at a time. Each jump skips a block that is never skipped the same way again, which gives amortized O(n).

Monotonic stack. Keep indices of bars with increasing heights. When a lower bar arrives, every taller bar on the stack has found its right limit (the new bar) and its left limit (the bar below it on the stack), so pop it and compute its area. A sentinel bar of height 0 at the end flushes the stack.

Maximal rectangle in a binary matrix. Process the matrix row by row. For each column keep the number of consecutive 1s ending at the current row: the length of the "hanging line" above that cell. Each row is then a histogram, and the best all-ones rectangle with its bottom edge on that row is the histogram's largest rectangle.

Min times something. The same left and right limits answer "maximize min(subarray) * sum(subarray)" (each element as the minimum, extended as far as it stays the minimum, scored with a prefix sum), and similar products.

When to use it in interviews / OAs

• "Largest rectangle in a histogram", "maximal rectangle of 1s", "count or measure submatrices of all 1s".
• "For each element, the nearest smaller element to the left and right", or "how far does each element remain the minimum (maximum)".
• Subarray scores built from the minimum: min-product, sum of subarray minimums, "maximum score of a good subarray".
• Building area or container problems where width and height interact (compare with trapping rain water, which uses running maxima instead).

Template

Left and right limits by hanging-line jumps

def span_limits(values: list[int]) -> tuple[list[int], list[int]]:
    """left[i], right[i]: the widest range around i where every value is >= values[i]."""
    n = len(values)
    left, right = list(range(n)), list(range(n))
    for i in range(n):
        while left[i] > 0 and values[left[i] - 1] >= values[i]:
            left[i] = left[left[i] - 1]  # jump over the neighbour's whole range
    for i in range(n - 1, -1, -1):
        while right[i] < n - 1 and values[right[i] + 1] >= values[i]:
            right[i] = right[right[i] + 1]
    return left, right


def largest_rectangle(heights: list[int]) -> int:
    left, right = span_limits(heights)
    return max((h * (right[i] - left[i] + 1) for i, h in enumerate(heights)), default=0)

The same answer with a monotonic stack

def largest_rectangle_stack(heights: list[int]) -> int:
    stack: list[int] = []  # indices of bars with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):  # the final 0 flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1  # between the new top and i, exclusive
            best = max(best, height * width)
        stack.append(i)
    return best

Maximal rectangle in a binary matrix

def maximal_rectangle(matrix: list[list[str]]) -> int:
    if not matrix:
        return 0
    heights = [0] * len(matrix[0])
    best = 0
    for row in matrix:
        for j, cell in enumerate(row):
            heights[j] = heights[j] + 1 if cell == "1" else 0  # length of the hanging line above
        best = max(best, largest_rectangle(heights))
    return best

Minimum times sum

For positive numbers, the best subarray for a given minimum nums[i] is the widest one in which it stays the minimum:

def max_min_product(nums: list[int]) -> int:
    """Maximum of min(subarray) * sum(subarray) over all non-empty subarrays (positive numbers)."""
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    left, right = span_limits(nums)
    return max(x * (prefix[right[i] + 1] - prefix[left[i]]) for i, x in enumerate(nums))

Complexity

• Histogram: O(n) time (amortized for the jump method), O(n) space.
• Maximal rectangle: O(rows * cols) time, O(cols) extra space.
• Min-product: O(n) time and space.
• An equivalent row-by-row DP keeps height, left and right arrays for each column and updates them from the previous row; it has the same O(rows * cols) cost.

Common pitfalls

• Width off by one. With inclusive limits the width is right - left + 1; with the stack, the width is i - stack[-1] - 1 (or i when the stack is empty).
• Equal heights. Using >= on both sides is fine for maximum area (equal bars find the same rectangle). For counting problems such as "sum of subarray minimums", use >= on one side and > on the other so each subarray is counted once.
• Forgetting the sentinel in the stack version, which leaves increasing bars unprocessed at the end.
• Resetting heights. A 0 in the matrix resets that column's height to 0; it does not just stop increasing.
• Overflow and modulo. Min-product values can exceed 64 bits in other languages for large inputs, and some versions ask for the maximum modulo 10^9 + 7: take the modulo after finding the maximum, not before.

Interview variations

• Largest rectangle in histogram: either template.
• Maximal rectangle (all 1s): histogram per row.
• Maximal square: a simpler DP, side[r][c] = 1 + min(top, left, top-left).
• Count submatrices with all ones: histogram per row, counting rectangles ending at each cell with a monotonic stack.
• Maximum subarray min-product and sum of subarray minimums: left and right limits with careful tie-breaking.
• Maximum score of a good subarray (the subarray must contain index k): expand greedily from k, or use the same limits.