How does a row-by-row column-height reduction turn a binary seat grid into one histogram scan per row?

## The setting A venue-booking view is a grid of seats, each free or taken, and the feature has to find the largest solid rectangular block of free seats — the biggest group that can be seated together. Naively this is a two-dimensional search: choose a top row, a bottom row, a left column and a right column, then verify. That is hopeless. The reduction turns it into a sequence of one-dimensional problems you already know how to solve. ## The reduction Keep one array `heights`, one slot per column, and sweep rows top to bottom: ``` for each row r: for each column c: if seat[r][c] is free: heights[c] = heights[c] + 1 else: heights[c] = 0 best = max(best, widest_block(heights)) ``` After processing row `r`, `heights[c]` is the number of consecutive free seats in column `c` ending at row `r`. Read the array as a silhouette of bars and it *is* a histogram — one whose baseline is row `r`. The widest solid block under that silhouette is precisely the widest all-free block whose bottom edge lies on row `r`. ## Why the maximum over rows is complete Every rectangle has exactly one bottom row. When the sweep reaches that row, the rectangle's columns all have height at least the rectangle's own height, so the histogram scan of that row can see it. Taking the maximum over all rows therefore considers every candidate at least once, and never invents a rectangle that does not exist — because a height of `k` in column `c` is a *proof* of `k` consecutive free seats there. Completeness and soundness both fall out of the definition of `heights`, which is the argument to give out loud. ## The reset is the whole correctness argument The single line that matters is `heights[c] = 0` at an occupied seat. Carry the height through a taken seat and the histogram now claims free depth across a booked seat; the algorithm will happily report a block straddling somebody's reservation. The reset is what makes a height mean *unbroken* freedom upward, and it is the first thing to check when the output looks too good. ## Cost, and the trap of recomputing Carrying `heights` across rows makes each row cost one pass to update plus one linear histogram scan — proportional to the number of columns. Over the whole grid that is proportional to the number of cells, which for venue-sized grids is nothing. The trap is recomputing each column's height from scratch by scanning upward from every cell. That is proportional to the number of rows per cell, multiplying the total by the row count for no benefit. The incremental carry is not a micro-optimisation; it is what keeps the reduction linear in the grid. ## What it does and does not buy The result is the largest **axis-aligned, contiguous** block. It is not the largest connected free region of arbitrary shape, and it is not the best seating arrangement under real constraints — aisles, price tiers, a group that will accept two adjacent rows. If the product needs those, the histogram reduction is the wrong tool and saying so is worth more than the clever code. That judgement — recognising when an elegant reduction answers a subtly different question than the one the product asked — is what the scenario is really testing. ## Updates in a live system Bookings arrive continuously. A single seat flipping to occupied changes `heights` only in that column, from that row downward until the next occupied seat — but the largest block can move anywhere, so no cheap local patch to the *answer* exists. In practice the whole sweep is re-run: for a venue-shaped grid it is microseconds, so recompute-on-change is the right default, and incremental cleverness here buys complexity rather than latency. If the grid grew to something where that stops being true, the honest move is to bound the query (largest block within a section, or largest block of at most a given size) rather than to preserve an exact global answer incrementally. ## Interview framing The expected answer is short: *maintain per-column free depth, reset at occupied cells, run the one-dimensional widest-block scan once per row, take the maximum.* Then volunteer the reset as the correctness hinge and the carry as the cost hinge. Candidates who have only memorised the one-dimensional scan can usually produce the sweep, but stumble when asked why the maximum over bottom rows misses nothing.