Seed tray footprint

The misting posts bolted through a propagation bench never move. The biggest tray that fits is rarely the widest free row.

The problem

A greenhouse propagation bench is a rectangle of planting cells. Some are unusable: a misting post is bolted through them, or a drainage cut-out crosses them. The rest are free.

Seed trays are rigid rectangles that sit square with the bench. One post under a tray lifts a corner and the tray drains unevenly, so a tray is placeable exactly when every cell beneath it is free. Find the largest tray this bench can take, in cells.

Input. bench — equal-length strings, top row first. '.' is free, '#' is blocked.

Output. The cell count of the largest bench-aligned rectangle of free cells, or 0 when every cell is blocked.

Example.

bench = [
    "..#..",
    ".....",
    "..#..",
    ".....",
]                                    ->  8

Columns 0 and 1 are free in all four rows, so a tray four deep and two across fits. The widest free run in any row is 5.

A second example, beating both the widest row and the largest square:

bench = [
    "#..#.",
    "...#.",
    "...#.",
]                                    ->  6

No row has a free run longer than 3, and the largest free square is four cells. The answer covers rows 1 and 2, columns 0 to 2.

Constraints.

• 1 <= len(bench) <= 1000
• 1 <= len(bench[0]) <= 1000
• every string in bench has the same length
• every character is '.' or '#'

Hints

Approach

Brute force

Pick a top row, a bottom row, a left column and a right column, then read every cell inside: about 2.5 × 10¹¹ candidate rectangles on a 1000 by 1000 bench, each costing up to 10⁶ reads.

The insight

Every free rectangle has a bottom row, and once that row is fixed the grid collapses to one bar chart: bar c counts the free cells running upward from this row in column c.

The predicate "this rectangle is entirely free" is no longer tested cell by cell — the depth array carries it, since a tray fits a span exactly when no bar in it is shallower. Sweeping the bottom row down the bench asks the bar-chart question once per row, and every free rectangle answers exactly one of them.

Algorithm

1. Keep depths, one entry per column, all zero.
2. For each row: add 1 to depths[c] when the cell is free, reset it to 0 when blocked.
3. Scan depths left to right holding a stack of indices with increasing depths, plus one imaginary depth of 0 past the last column.
4. While the incoming depth is not greater than the top of the stack, pop. The popped bar spans from the index below it to the incoming index, both exclusive; its area is depth times width.
5. The largest area over all rows is the answer.

Complexity

Time O(rows · cols) — one linear update and one stack pass per row, each column pushed and popped once. Space O(cols) — depths and stack; the bench is never copied.

Solution

"""Seed tray footprint — per-row depth histograms scanned with a monotonic stack."""


def widest_block(depths):
    """Largest all-free rectangle whose bottom edge is the current bench row.

    `depths[c]` is how many free cells stack upward from this row in column c.
    Invariant: the stack holds column indices whose depths strictly increase,
    so the moment a shallower column arrives, every popped column has both its
    left and right walls known and its best rectangle can be measured once.
    """
    best = 0
    stack = []
    for right in range(len(depths) + 1):
        depth = 0 if right == len(depths) else depths[right]
        while stack and depths[stack[-1]] >= depth:
            top = stack.pop()
            left = stack[-1] if stack else -1
            # Column `top` cannot extend past `left` or reach `right`.
            best = max(best, depths[top] * (right - left - 1))
        stack.append(right)
    return best


def solve(bench):
    if not bench or not bench[0]:
        return 0
    width = len(bench[0])
    depths = [0] * width
    best = 0
    for row in bench:
        for c in range(width):
            # A post resets the column; free cells extend the run downward.
            depths[c] = depths[c] + 1 if row[c] == "." else 0
        best = max(best, widest_block(depths))
    return best

TESTS = [
    ((["..#..", ".....", "..#..", "....."],), 8),
    ((["#..#.", "...#.", "...#."],), 6),
    ((["#.#"],), 1),
    ((["##", "##"],), 0),
    ((["....", "....", "...."],), 12),
    ((["#..", ".#.", "..#"],), 2),
    (([".."],), 2),
]

Pitfalls

• Carrying a column's depth past a post rather than resetting to zero. The tray straddles the post, and the first example reports 10.
• Stopping the stack pass at the last column. Bars left on the stack go unmeasured, so ["...."] gives 3 instead of 4.
• Measuring a popped bar's width as right - top, from the bar's own index instead of the left wall below it. That drops everything the bar extends over to its left, and the first example returns 4, not 8.

Variants

• First red build — the same refusal to repeat a check, on a structure handed to you rather than built.
• Drop the outer sweep and the bar chart is the whole input; the stack pass is unchanged.